Algorithm8.1 BFS
[TOC]
bfs
[模版] 最多可到达
https://www.luogu.com.cn/problem/P1683
题目大意：最多可到达的格点数
#include <iostream>
using namespace std;
#define maxn 23
int n, m, dir[4][2]={{0, 1}, {0, -1}, {1, 0}, {-1, 0}}, ans=1, vis[maxn][maxn];
char mp[maxn][maxn];
#include <queue>
struct node{
int x, y;
node(int x,int y): x(x), y(y){}
};
queue<node> q;
void bfs(int x, int y) {
q.push(node(x, y));
vis[x][y] = 1;
while (!q.empty()) {
node nw = q.front();q.pop();
for (int i = 0; i < 4; ++i) {
int nx = nw.x+dir[i][0], ny = nw.y+dir[i][1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && mp[nx][ny] == '.' && !vis[nx][ny]) {
vis[nx][ny] = 1;
q.push(node(nx, ny));
ans++;
}
}
}
printf("%d\n", ans);
}
int main() {
scanf("%d%d", &m, &n);
for (int i = 0; i < n; ++i) scanf("%s", mp[i]);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (mp[i][j] == '@') bfs(i, j);
return 0;
}
最少步数
https://www.luogu.com.cn/problem/P1746
题目大意：从地图上的起点到终点所需要的最少步数
1、在模版的基础上，对结构体（也就是node）增加一个属性val，用来记录蔓延到当前的点所需要的步数。
2、还是要去维护一个vis数组来避免重复猜，虽然最短步数=>到了终点立马跳出，但是如果一直到不了的话，不加vis数组就永远跳不出。
#include <iostream>
using namespace std;
#define maxn 1005
int n, bgx, bgy, edx, edy, dir[4][2]={{0, 1}, {0, -1}, {1, 0}, {-1, 0}}, vis[maxn][maxn];
char mp[maxn][maxn];
#include <queue>
struct node{
int x, y, val;
node(int x, int y, int val): x(x), y(y), val(val){}
};
queue<node> q;
void bfs(int x, int y) {
q.push(node(x, y, 0));
vis[x][y] = 1;
while (!q.empty()) {
node nw = q.front();q.pop();
if (nw.x == edx-1 && nw.y == edy-1) {printf("%d\n", nw.val);return;}
for (int i = 0; i < 4; ++i) {
int nx = nw.x+dir[i][0], ny = nw.y+dir[i][1];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && mp[nx][ny] == '0' && !vis[nx][ny]) {
vis[nx][ny] = 1;
q.push(node(nx, ny, nw.val+1));
}
}
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%s", mp[i]);
scanf("%d%d%d%d", &bgx, &bgy, &edx, &edy);
bfs(bgx-1, bgy-1);
return 0;
}
最短路径
（同时也可以顺手算上最短步数）
http://poj.org/problem?id=3984（未ac）
题目大意：给出一个01迷宫，求起到终点的路径
1、记录路径的思路：通过在结构体中，定义一个指向其他节点的指针，指向者就是从谁哪里来到的这个点。
2、在绑定每一层的指向关系的时候，直接通过队列拿出来的&q.front()去指向，而不是先node nw = q.front();赋值，然后再把&nw去赋值
3、在最后搜索完成之后，从终点 顺着每个node的fa指针，找到是哪个节点到这个节点的，然后一步一步找回去，最后再逆序输出即可。
#include <iostream>
using namespace std;
#define maxn 20
int mp[maxn][maxn], vis[maxn][maxn], dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, ansx[300], ansy[300], idx;
struct node{
int x, y;
node * fa;
node(){}
node(int x, int y, node * fa): x(x), y(y), fa(fa){}
};
#include <queue>
queue<node> q;
void printTrace(node nw){
ansx[idx] = nw.x;ansy[idx++] = nw.y;
node * nt = nw.fa;
while (nt!=NULL) {
ansx[idx] = nt->x;ansy[idx++] = nt->y;
nt = nt->fa;
}
for (int i = idx-1; i >= 0; --i) printf("(%d, %d)\n",ansx[i], ansy[i]);
}
void bfs(int x, int y) {
q.push(node(x, y, NULL));
while (!q.empty()) {
node nw = q.front();
if (nw.x == 4 && nw.y == 4) {printTrace(nw);return;}
for (int i = 0; i < 4; ++i) {
int nx = nw.x+dir[i][0], ny = nw.y+dir[i][1];
if (nx == 4 && ny == 4) {printTrace(node(nx, ny, &nw));return;}
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !mp[nx][ny] && !vis[nx][ny]) {
vis[nx][ny] = 1;
q.push(node(nx, ny, &q.front()));
}
}
q.pop();
}
}
int main() {
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 5; ++j)
scanf("%d", &mp[i][j]);
bfs(0,0);
return 0;
}
AC代码：
通过在节点中添加一个属性pre，用来表示这个节点的前继节点是谁。
易错：在创建bfs的数据结构queue的时候，队列中的数据类型应该是指向结构体的指针，所以应该表示为queue<node *> q;
区分结构体与指向结构体的指针，在写代码的过程中，可以发现指向结构体的指针在调用其属性时是通过->进行调用，而结构体是通过.进行调用
#include <iostream>
using namespace std;
int mp[6][6], dir[4][2]={{0, 1}, {0, -1}, {1, 0}, {-1, 0}}, vis[6][6];
struct node {
int x, y;
node * pre;
};
#include <vector>
vector<pair<int, int>> b;
void printtrack(node * nw) {
while (nw) {
b.push_back(make_pair(nw->x, nw->y));
nw = nw->pre;
}
for (int i = b.size()-1; i >= 0; --i) printf("(%d, %d)\n", b[i].first-1, b[i].second-1);
}
#include <queue>
queue<node *> q;
void bfs(){
vis[1][1] = 1;
node * tmnode = new node;
tmnode->x = 1, tmnode->y = 1, tmnode->pre = NULL;
q.push(tmnode);
while (!q.empty()) {
node * nw = q.front();q.pop();
if (nw->x == 5 && nw->y == 5) {printtrack(nw);return;}
for (int i = 0; i < 4; ++i) {
int nx = nw->x+dir[i][0], ny = nw->y+dir[i][1];
if (!vis[nx][ny] && !mp[nx][ny] && nx >= 1 && nx <= 5 && ny >= 1 && ny <= 5) {
node * ntnode = new node();
ntnode->x = nx, ntnode->y = ny;ntnode->pre = nw;
vis[nx][ny] = 1; q.push(ntnode);
}
}
}
}
int main() {
for (int i = 1; i <= 5; ++i)
for (int j = 1; j <= 5; ++j)
scanf("%d", &mp[i][j]);
bfs();
return 0;
}
[基本]联通块数
https://www.luogu.com.cn/problem/P1596
bfs实现 // dfs也可以实现，只不过是不同的搜索策略
#include <iostream>
using namespace std;
#define maxn 105
int n, m, cnt, dir[8][2] = {{1, 0}, {-1, 0}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}, {0, 1}, {0, -1}};
char a[maxn][maxn];
struct node{
int x, y;
node(int x, int y): x(x), y(y){}
};
#include <queue>
queue<node>q;
void bfs(int x, int y) {
a[x][y] = '.';
q.push(node(x, y));
while (!q.empty()) {
node nw = q.front();q.pop();
for (int i = 0; i < 8; ++i) {
int nx = nw.x + dir[i][0], ny = nw.y+dir[i][1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] == 'W') {a[nx][ny] = '.';q.push(node(nx, ny));}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) scanf("%s", a[i]);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (a[i][j] == 'W') {cnt++;bfs(i, j);}
printf("%d\n", cnt);
return 0;
}
联通块数 + 染色
01迷宫-可到达的方块总数：https://www.luogu.com.cn/problem/P1141 (未ac)
题目大意：一个地图上标有0和1的迷宫，移动规则为仅能从0移动到1或者从1移动到0。问最多可以移动到多少个地方。
1、移动规则的约束：通过异或来判断。mp[nwn.x][nwn.y]^mp[nx][ny]，异或结果为1，那就是满足移动前和移动完之后的那两个位置不同，满足01或者10。
2、时间限制：由于会多次查询，时间会爆掉，所以通过联通块染色。染色方式有两种：
- 同种的直接给标记上这种的总个数。=>不能在bfs的过程中就标记上，要在过程中用容器给储存起来，等彻底延伸完了再重新遍历一边容器然后染色。
- 用一个自增数组，然后在遍历的过程中把索引标记给每个点，最后再利用索引去自增数组中找答案。
#include <iostream>
using namespace std;
struct node{
int x, y;
node(int x, int y):x(x), y(y){}
};
#include <queue>
queue<node> q;
#define maxn 1200
int n, m, tx, ty, mp[maxn][maxn], ans = 0, dir[4][2]={{0, 1}, {0, -1}, {1, 0}, {-1, 0}}, vis[maxn][maxn], block[maxn][maxn] ,cnt[1000100], idx = 1;
char s[maxn];
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))
#include <vector>
//vector<node> kp;
void bfs(int x, int y){
while (!q.empty()){
node nwn = q.front();q.pop();
for (int i = 0; i < 4; ++i) {
int nx = nwn.x+dir[i][0], ny = nwn.y+dir[i][1];
if (nx > 0 && nx <= n && ny > 0 && ny <= n && !vis[nx][ny] && mp[nwn.x][nwn.y]^mp[nx][ny]){
ans++;
vis[nx][ny] = 1;
block[nx][ny] = idx;
q.push(node(nx, ny));
// kp.push_back(node(nx, ny));
}
}
}
// 染色
// for (int i = 0; i < kp.size(); ++i) block[kp[i].x][kp[i].y] = ans;
cnt[idx++] = ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
scanf("%s", s);
for (int j = 0; j < n; ++j) {
if (s[j] == '0') mp[i+1][j+1] = 0;
else mp[i+1][j+1] = 1;
}
}
while (m--) {
ans = 1;cl(vis, 0);
scanf("%d%d", &tx, &ty);
if (block[tx][ty]) {printf("%d\n", cnt[block[tx][ty]]);continue;}
vis[tx][ty] = 1;
block[tx][ty] = idx;
q.push(node(tx, ty));
// kp.push_back(node(tx, ty));
bfs(tx, ty);
printf("%d\n", ans);
}
return 0;
}