池塘计数（bfs）
农夫约翰有一片 N∗M 的矩形土地。
最近，由于降雨的原因，部分土地被水淹没了。
现在用一个字符矩阵来表示他的土地。
每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。
现在，约翰想知道他的土地中形成了多少片池塘。
每组相连的积水单元格集合可以看作是一片池塘。
每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。
请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。
输入格式
第一行包含两个整数 N 和 M。
接下来 N 行，每行包含 M 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。
输出格式
输出一个整数，表示池塘数目。
数据范围
1≤N,M≤1000
输入样例：
10 12
W…WW.
.WWW…WWW
…WW…WW.
…WW.
…W…
…W…W…
.W.W…WW.
W.W.W…W.
.W.W…W.
…W…W.
输出样例：
3
#include<iostream>
#include<queue>
using namespace std;
const int N = 1010;
char a[N][N];
int n,m,v[N][N],ans=0;
queue<pair<int,int>> q;
void bfs(int x,int y)
{
q.push({x,y});
v[x][y]=true;
while(!q.empty())
{
auto t=q.front();
q.pop();
for(int i=t.first-1;i<=t.first+1;i++)
{
for(int j=t.second-1;j<=t.second+1;j++)
{
if(i==t.first&&j==t.second) continue;
if(i<0||i>=n||j<0||j>=m) continue;
if(a[i][j]!='W'||v[i][j]) continue;
v[i][j]=true;
q.push({i,j});
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]=='W'&&!v[i][j])
{
bfs(i,j);
ans++;
}
}
}
cout<<ans<<endl;
}
池塘计数（dfs)
#include<iostream>
#include<queue>
using namespace std;
const int N = 1010;
char a[N][N];
int n,m,v[N][N],ans=0;
queue<pair<int,int>> q;
void dfs(int x,int y)
{
if(x<0||x>=n||y<0||y>=m) return ;
if(a[x][y]!='W') return;
a[x][y]='.';
dfs(x-1,y-1);
dfs(x-1,y);
dfs(x-1,y+1);
dfs(x,y-1);
dfs(x,y+1);
dfs(x+1,y-1);
dfs(x+1,y);
dfs(x+1,y+1);
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]=='W')
{
dfs(i,j);
ans++;
}
}
}
cout<<ans<<endl;
}
迷宫问题
给定一个 n×n 的二维数组，如下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
数据保证至少存在一条从左上角走到右下角的路径。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。
输出格式
输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。
按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)。
数据范围
0≤n≤1000
输入样例：
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
#include<iostream>
#include<queue>
using namespace std;
const int N = 1010;
int n;
queue<pair<int,int>> q;
pair<int,int> pre[N][N];
int a[N][N],v[N][N];
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
void bfs(int x,int y)
{
q.push({x,y});
pre[x][y]={0,0};
while(!q.empty())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x<0||x>=n||y<0||y>=n) continue;
if(a[x][y]==1||v[x][y]==true) continue;
v[x][y]=true;
q.push({x,y});
pre[x][y]=t;
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
}
bfs(n-1,n-1);
pair<int,int> t(0,0);
while(1)
{
cout<<t.first<<" "<<t.second<<endl;
if(t.first==n-1&&t.second==n-1) break;
t=pre[t.first][t.second];
}
}
武士风度的牛
农民 John 有很多牛，他想交易其中一头被 Don 称为 The Knight 的牛。
这头牛有一个独一无二的超能力，在农场里像 Knight 一样地跳（就是我们熟悉的象棋中马的走法）。
虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个 x，y 的坐标图来表示。
这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了 The Knight 的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。
现在你的任务是，确定 The Knight 要想吃到草，至少需要跳多少次。
The Knight 的位置用 K 来标记，障碍的位置用 * 来标记，草的位置用 H 来标记。
这里有一个地图的例子：
11 | . . . . . . . . . .
10 | . . . . * . . . . .
9 | . . . . . . . . . .
8 | . . . * . * . . . .
7 | . . . . . . . * . .
6 | . . * . . * . . . H
5 | * . . . . . . . . .
4 | . . . * . . . * . .
3 | . K . . . . . . . .
2 | . . . * . . . . . *
1 | . . * . . . . * . .
0 ----------------------
1
0 1 2 3 4 5 6 7 8 9 0
The Knight 可以按照下图中的 A,B,C,D… 这条路径用 5 次跳到草的地方（有可能其它路线的长度也是 5）：
11 | . . . . . . . . . .
10 | . . . . * . . . . .
9 | . . . . . . . . . .
8 | . . . * . * . . . .
7 | . . . . . . . * . .
6 | . . * . . * . . . F<
5 | * . B . . . . . . .
4 | . . . * C . . * E .
3 | .>A . . . . D . . .
2 | . . . * . . . . . *
1 | . . * . . . . * . .
0 ----------------------
1
0 1 2 3 4 5 6 7 8 9 0
注意： 数据保证一定有解。
输入格式
第 1 行： 两个数，表示农场的列数 C 和行数 R。
第 2…R+1 行: 每行一个由 C 个字符组成的字符串，共同描绘出牧场地图。
输出格式
一个整数，表示跳跃的最小次数。
数据范围
1≤R,C≤150
输入样例：
10 11
…
……
…
….…
……
………H
…
………
.K…
……*
………
输出样例：
5
#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;
const int N = 200;
queue<pair<int,int>> q;
char a[N][N];
int d[N][N],v[N][N];
int n,m;
int dx[]={1,2,2,1,-1,-2,-2,-1},dy[]={2,1,-1,-2,2,1,-1,-2};
int bfs(int x,int y)
{
q.push({x,y});
v[x][y]=true;
while(!q.empty())
{
auto t=q.front();
q.pop();
for(int i=0;i<8;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x<0||x>=n||y<0||y>=m) continue;
if(v[x][y]) continue;
if(a[x][y]=='*') continue;
if(a[x][y]=='H') return d[t.first][t.second]+1;
d[x][y]=d[t.first][t.second]+1;
v[x][y]=true;
q.push({x,y});
}
}
return 0;
}
int main()
{
cin>>m>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]=='K')
{
cout<<bfs(i,j);
return 0;
}
}
}
}
抓住那头牛
农夫知道一头牛的位置，想要抓住它。
农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。
农夫有两种移动方式：
从 X 移动到 X−1 或 X+1，每次移动花费一分钟
从 X 移动到 2∗X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。
农夫最少要花多少时间才能抓住牛？
输入格式
共一行，包含两个整数N和K。
输出格式
输出一个整数，表示抓到牛所花费的最少时间。
数据范围
0≤N,K≤105
输入样例：
5 17
输出样例：
4
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 200007;
int d[N],v[N],n,m;
queue<int> q;
int dfs()
{
q.push(n);
v[n]=true;
while(!q.empty())
{
int t=q.front();
q.pop();
if(t+1<N&&v[t+1]==false)
{
d[t+1]=d[t]+1;
v[t+1]=true;
q.push(t+1);
}
if(t-1>=0&&v[t-1]==false)
{
d[t-1]=d[t]+1;
v[t-1]=true;
q.push(t-1);
}
if(2*t<N&&v[2*t]==false)
{
d[2*t]=d[t]+1;
v[2*t]=true;
q.push(2*t);
}
if(t==m) return d[t];
}
return -1;
}
int main()
{
cin>>n>>m;
cout<<dfs();
}
填充颜色
#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int n,m,v[N][N];
int a[N][N];
queue<pair<int,int>> q;
int ans=0;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
void bfs(int x,int y)
{
q.push({x,y});
v[x][y]=true;
while(!q.empty())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
if(a[x][y]==0) //先特判自己是不是0
{
a[x][y]=2;
v[x][y]=true;
q.push({x,y});
}
//再特判自己的上下左右
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x<0||x>=n||y<0||y>=m) continue;
if(v[x][y]||a[x][y]!=0) continue;
if(a[x][y]==0)
{
a[x][y]=2;
v[x][y]=true;
q.push({x,y});
}
}
}
}
int main()
{
cin>>n;
m=n;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]==1)
{
bfs(i+1,j+1); //如果当前为1，则从1的右下角开始遍历
//因为只有一个闭环，所以出来就打印返回
for(int p=0;p<n;p++)
{
for(int q=0;q<m;q++)
{
cout<<a[p][q]<<" ";
}
cout<<endl;
}
return 0;
}
}
}
}
拯救oibh总部（边界注水）
思路：
从四个边界注水，如果被淹到了就设置为1，最后遍历剩余0的数量即可
住：不可以对所有数据进行bfs，会把所有0变成1
#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int n,m,v[N][N];
char a[N][N];
queue<pair<int,int>> q;
int ans=0;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
void bfs(int x,int y)
{
q.push({x,y});
v[x][y]=true;
while(!q.empty())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
if(a[x][y]=='0') //自我判断
{
v[x][y]=true;
a[x][y]='1';
q.push({x,y});
}
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x<0||x>=n||y<0||y>=m) continue;
if(v[x][y]||a[x][y]!='0') continue;
v[x][y]=true;
a[x][y]='1';
q.push({x,y});
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
for(int j=0;j<m;j++) //从上下边界注水
{
if(a[0][j]=='0'&&!v[0][j]) bfs(0,j);
if(a[n-1][j]=='0'&&!v[n-1][j]) bfs(n-1,j);
}
for(int i=0;i<n;i++) //从左右边界注水
{
if(a[i][0]=='0'&&!v[i][0]) bfs(i,0);
if(a[i][m-1]=='0'&&!v[i][m-1]) bfs(i,m-1);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]=='0') ans++;
}
}
cout<<ans;
}
矩阵距离（多源bfs）
给定一个 N 行 M 列的 01 矩阵 A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：
dist(A[i][j],A[k][l])=|i−k|+|j−l|
输出一个 N 行 M 列的整数矩阵 B，其中：
B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])
输入格式
第一行两个整数 N,M。
接下来一个 N 行 M 列的 01 矩阵，数字之间没有空格。
输出格式
一个 N 行 M 列的矩阵 B，相邻两个整数之间用一个空格隔开。
数据范围
1≤N,M≤1000
输入样例：
3 4
0001
0011
0110
输出样例：
3 2 1 0
2 1 0 0
1 0 0 1
#include<iostream>
using namespace std;
#include<cstring>
#include<queue>
const int N = 1010;
int n,m,d[N][N],a[N][N],v[N][N];
queue<pair<int,int>> q;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
void bfs()
{
while(!q.empty())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x<0||x>=n||y<0||y>=m) continue;
if(v[x][y]) continue;
q.push({x,y});
d[x][y]=d[t.first][t.second]+1;
v[x][y]=true;
}
}
}
int main()
{
cin>>n>>m;
memset(d,-1,sizeof(d));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
char c;
cin>>c;
if(c=='1')
{
a[i][j]=c-'0';
v[i][j]=true;
d[i][j]=0;
q.push({i,j});
}
else
{
a[i][j]=c-'0';
}
}
}
bfs();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<d[i][j]<<" ";
}
cout<<endl;
}
}
血色先锋队(曼哈顿距离)
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
int n,k,m,ans,sum;
int ax[N],ay[N],bx,by;
int main()
{
cin>>n>>m;
int a,b;
cin>>a>>b;
for(int i=0;i<a;i++)
{
cin>>ax[i]>>ay[i];
}
while(b--)
{
cin>>bx>>by;
ans=0x3f3f3f3f;
for(int i=0;i<a;i++)
{
ans=min(ans,abs(ax[i]-bx)+abs(ay[i]-by));
}
cout<<ans<<endl;
}
}
Cow Picnic S(图的bfs)
#include<bits/stdc++.h>
using namespace std;
const int N=10000;
int n,k,m,ans,sum[N]; //sum[i]表示i号牧场有多少牛可以到达
int v[N];
queue<int> q;
int st[N]; //牛所在牧场编号
int head[N],to[N],w[N],nxt[N],i=0;
void add(int a,int b,int c)
{
to[i]=b;
w[i]=c;
nxt[i]=head[a];
head[a]=i++;
}
void bfs(int k) //k为牧场号
{
q.push(k);
v[k]=true;
while(!q.empty())
{
int t=q.front();
q.pop();
for(int i=head[t];i!=-1;i=nxt[i])
{
int j=to[i]; //j为当前牧场的下一个牧场号
if(!v[j])
{
q.push(j);
sum[j]++;
v[j]=true;
}
}
}
}
int main()
{
cin>>k>>n>>m;
memset(head,-1,sizeof(head));
for(int i=1;i<=k;i++)
{
cin>>st[i];
sum[st[i]]++;
}
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
add(x,y,1);
}
for(int i=1;i<=k;i++)
{
memset(v,0,sizeof(v)); //对所有牛进行扩展，找出能到的牧场数
bfs(st[i]);
}
for(int i=1;i<=n;i++)
{
if(sum[i]==k) ans++; //如果当前牧场可到的牛的数量等于所有牛
} //说明所有牛都可以到，答案+
cout<<ans;
}
Q.E.D.