bfs模板
1.全球变暖
你有一张某海域 N×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
…###.
.......
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 2 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入格式
第一行包含一个整数N。
以下 N 行 N 列，包含一个由字符”#”和”.”构成的 N×N 字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。
照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。
输出格式
一个整数表示答案。
数据范围
1≤N≤1000
输入样例1：
7
.......
.##....
.##....
....##.
..####.
...###.
.......
输出样例1：
1
输入样例2：
9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........
输出样例2：
1
#include<iostream>
using namespace std;
#define x first
#define y second
const int N = 1000 + 10;
int n;
typedef pair<int,int> PII;
PII q[N*N];
bool st[N][N];
char g[N][N];
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
void bfs(int sx,int sy,int &total,int &bound){
int tt = 0,hh = 0;
st[sx][sy] = true;
q[0] = {sx,sy};
while(hh <= tt){
PII t = q[hh ++];
total ++;
bool is_bound = false;//是否连着海
for(int i = 0;i < 4;i++){//四个方向判断一个 #
int x = t.x + dx[i],y = t.y + dy[i];
if(x < 0 || x>=n || y < 0 || y >= n || st[x][y]) continue;
if(g[x][y] == '.'){
is_bound = true;
continue;
}
st[x][y] = true;
q[++tt] = {x,y};//先加和后加确实不同要注意
}
if(is_bound) bound++;
}
}
int main(){
cin >> n;
for(int i = 0;i < n;i++){
cin >> g[i];
}
int cnt = 0;
//先找有几个连通块，给每个格子打上标记
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++){
if(!st[i][j] && g[i][j] == '#'){
int total = 0,bound = 0;
bfs(i,j,total,bound);
if(total == bound) cnt ++;
}
}
cout << cnt << endl;
return 0;
}
2.地牢大师
你现在被困在一个三维地牢中，需要找到最快脱离的出路！
地牢由若干个单位立方体组成，其中部分不含岩石障碍可以直接通过，部分包含岩石障碍无法通过。
向北，向南，向东，向西，向上或向下移动一个单元距离均需要一分钟。
你不能沿对角线移动，迷宫边界都是坚硬的岩石，你不能走出边界范围。
请问，你有可能逃脱吗？
如果可以，需要多长时间？
输入格式
输入包含多组测试数据。
每组数据第一行包含三个整数 L,R,C 分别表示地牢层数，以及每一层地牢的行数和列数。
接下来是 L 个 R 行 C 列的字符矩阵，用来表示每一层地牢的具体状况。
每个字符用来描述一个地牢单元的具体状况。
其中, 充满岩石障碍的单元格用”#”表示，不含障碍的空单元格用”.”表示，你的起始位置用”S”表示，终点用”E”表示。
每一个字符矩阵后面都会包含一个空行。
当输入一行为”0 0 0”时，表示输入终止。
输出格式
每组数据输出一个结果，每个结果占一行。
如果能够逃脱地牢，则输出”Escaped in x minute(s).”，其中X为逃脱所需最短时间。
如果不能逃脱地牢，则输出”Trapped!”。
数据范围
1≤L,R,C≤100
输入样例：
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
输出样例：
Escaped in 11 minute(s).
Trapped!
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
struct Points{
int x,y,z;
}q[N*N*N];
int k,r,c;
int dist[N][N][N];
int dx[6] = {1,-1,0,0,0,0},dy[6] = {0,0,1,-1,0,0},dz[6] = {0,0,0,0,1,-1};
char g[N][N][N];
int bfs(Points start,Points end){
int hh = 0,tt = 0;
memset(dist,-1,sizeof dist);
q[0] = start;
dist[start.x][start.y][start.z] = 0;
while(hh <= tt){
Points t = q[hh++];
for(int i = 0;i < 6;i++){
int x = t.x + dz[i],y = t.y + dx[i],z = t.z + dy[i];
if(x < 0 || x >= k || y < 0 || y >= r || z < 0 || z >= c || dist[x][y][z] != -1 || g[x][y][z] == '#') continue;
dist[x][y][z] = dist[t.x][t.y][t.z] + 1;
if(x == end.x && y == end.y && z == end.z) return dist[x][y][z];
q[++tt] = {x,y,z};
}
}
return -1;
}
int main(){
while(cin >> k >> r >> c,k||c||r){
Points start,end;
for(int i = 0;i < k;i++)
for(int j = 0;j < r;j++){
cin >> g[i][j];
for(int w = 0;w < c;w++){
if(g[i][j][w] == 'S') start = {i,j,w};
else if(g[i][j][w] == 'E') end = {i,j,w};
}
}
int distance = bfs(start,end);
if(distance == -1) cout << "Trapped!" << endl;
else cout << "Escaped in "<< distance <<" minute(s)." << endl;
}
return 0;
}
3.献给阿尔吉侬的花束
阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。
今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。
现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。
迷宫用一个 R×C 的字符矩阵来表示。
字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 # 表示墙壁，字符 . 表示可以通行。
阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。
输入格式
第一行是一个正整数 T，表示一共有 T 组数据。
每一组数据的第一行包含了两个用空格分开的正整数 R 和 C，表示地图是一个 R×C 的矩阵。
接下来的 R 行描述了地图的具体内容，每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。
输出格式
对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。
若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。
每组数据的输出结果占一行。
数据范围
1<T≤10,
2≤R,C≤200
输入样例：
3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.
输出样例：
5
1
oop!
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 210;
typedef pair<int,int> PII;
#define x first
#define y second
int T,n,m;
char g[N][N];
int dist[N][N];
bool st[N][N];
int bfs(PII start,PII end){
queue<PII> q;
memset(dist,-1,sizeof dist);
dist[start.x][start.y] = 0;
q.push(start);
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
while(q.size()){
auto t = q.front();
q.pop();
for(int i = 0;i < 4;i++){
int x = t.x + dx[i],y = t.y + dy[i];
if(x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '#' || dist[x][y] != -1) continue;
dist[x][y] = dist[t.x][t.y] + 1;
if(end == make_pair(x,y)) return dist[x][y];
q.push({x,y});
}
}
return -1;
}
int main(){
scanf("%d",&T);
while(T --){
scanf("%d%d",&n,&m);
for(int i = 0;i < n;i++) scanf("%s",g[i]);
PII start,end;
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)//bug
{
if(g[i][j] == 'S') start = {i,j};
else if(g[i][j] == 'E') end = {i,j};
}
int distance = bfs(start,end);
if(distance == -1) printf("%s\n","oop!");
else printf("%d\n",distance);
}
return 0;
}
