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;
}