2.25DFS和BFS刷题

洛谷P1101单词方阵：用sta存字符串，for找到‘y'的位置，然后dfs对字符串用for进行一个一个的判断，不符合就return，下面再用for进行book标记，能执行下面的for说明上面没有return，所以说明找到，book标记字符串长度就行，然后for＋if判断book为true就输出，不然就输出*就行。

#include<iostream>
#include<cstring>
using namespace std;
const int N = 105;
int n;
string sta = "yizhong";
char ch[N][N];
bool book[N][N];
int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
void dfs(int x, int y, int xd, int yd){
	int a = x + xd, b = y + yd;
	for(int i = 1; i < 7; i++){
		if(sta[i] != ch[a][b])return;
		a += xd;
		b += yd;
	}
	for(int i = 0; i < 7; i++){
		book[x][y] = true;
		x += xd;
		y += yd;
	} 
}
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin >> ch[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(ch[i][j] == 'y'){
				for(int k = 0; k < 8; k++) dfs(i, j, dx[k], dy[k]);
			} 
		} 
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(book[i][j]) cout << ch[i][j];
			else cout << '*' ;
		}
		cout << endl;
	}
	
	return 0;
}

洛谷P2404自然数的拆分问题：DFS

#include<iostream>
using namespace std;
int n, m;
int p[15] = {1};
void dfs(int x){
	for(int i = p[x - 1]; i <= m; i++){
		if(i == n)continue;
		p[x] = i;
		m -= i;
		if(m == 0){
			for(int j = 1; j < x; j++){
				cout << p[j] << '+';
			}
			cout << p[x] << endl;
		}
		else dfs(x + 1);
		m += i;
	}
}
int main(){
	cin >> n;
	m = n;
	dfs(1);
	
	return 0;
}

洛谷P1596一道BFS，求连通块数量。

#include<iostream>
#include<queue>
using namespace std;
const int N = 105;
int n, m;
bool st[N][N];
char ch[N][N];
int ans;
int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
typedef pair<int, int> PII;
void bfs(int a, int b){
	queue<PII> q;
	q.push({a, b});
	st[a][b] = true;
	while(q.size()){
		auto t = q.front();
		q.pop();
		int x = t.first, y = t.second;
		for(int i = 0; i < 8; i++){
			int xx = x + dx[i], yy = y + dy[i];
			if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && !st[xx][yy] && ch[xx][yy] == 'W'){
				st[xx][yy] = true;
				q.push({xx, yy});
			}
		}
	}
	ans++;
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> ch[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(ch[i][j] == 'W' && !st[i][j])bfs(i, j);
		}
	}
	cout << ans << endl;
	return 0;
}

洛谷P1162填色：相当于围墙加水，里面的是水也就是2， 外面的为0，外面从0，0开始把围墙外的数通过BFS都给标记成3，然后是3就输出0，原来的围墙1不变，然后围墙里面本来是0，的就输出2。

#include<iostream>
#include<queue>
using namespace std;
const int N = 35;
int a[N][N];
int n;
bool st[N][N];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
typedef pair<int, int> PII; 
void bfs(){
	queue<PII> q;
	q.push({0, 0});
	st[0][0] = true;
	while(q.size()){
		auto t = q.front();
		q.pop();
		int x = t.first, y = t.second;
		for(int i = 0; i < 4; i++){
			int xx = x + dx[i], yy = y + dy[i];
			if(xx >= 0 && xx <= n + 1 && yy >= 0 && yy <= n + 1 && !st[xx][yy] && a[xx][yy] == 0){
				a[xx][yy] = 3;
				st[xx][yy] = true;
				q.push({xx, yy});
			}
		}
	}
}
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin >> a[i][j];
		}
	}
	bfs();
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(a[i][j] == 3) cout << 0 << ' ';
			else if(a[i][j] == 1) cout << 1 << ' ';
			else cout << 2 << ' '; 
		}
		cout << endl;
	}
	return 0;
}