可以使用BFS或者DFS方法解决的迷宫问题！
题目如下：
kotori在一个n*m迷宫里，迷宫的最外层被岩浆淹没，无法涉足，迷宫内有k个出口。kotori只能上下左右四个方向移动。她想知道有多少出口是她能到达的，最近的出口离她有多远？
输入描述:
第一行为两个整数n和m，代表迷宫的行和列数 (1≤n,m≤30) 后面紧跟着n行长度为m的字符串来描述迷宫。'k'代表kotori开始的位置，'.'代表道路，'*'代表墙壁，'e'代表出口。保证输入合法。
输出描述:
若有出口可以抵达，则输出2个整数，第一个代表kotori可选择的出口的数量，第二个代表kotori到最近的出口的步数。（注意，kotori到达出口一定会离开迷宫） 若没有出口可以抵达，则输出-1。
示例1
#include<iostream>
#include<string.h>
using namespace std;
char map[][];
int use[][];
int dir[][] = {{,},{,},{,-},{-,}}; //上下左右四个方向
int minn = ; int pan(int x,int y)
{
if( <= x && x <= && <= y && y <= && (map[x][y] == '.' || map[x][y]=='k')) return ;
else return ;
} void dfs(int x,int y,int step)
{
// 递归程序，必须要设置整个程序的出口，在dfs中，即当走到迷宫出口处即可结束程序
if(map[x][y] == 'e')
{
cout<<"success"<<endl;
if(step < minn) minn = step;
return;
}
for(int i = ; i < ; i++)
{
if(pan(x,y) && use[x][y] != )
{
use[x][y] = ;
cout<<"dd";
cout<<" "<<map[x+dir[i][]][y+dir[i][]]<<endl;
dfs(x+dir[i][],y+dir[i][],step+);
use[x][y] = ;
}
} }
int main()
{
int n;
int m;
cin >> n >> m;
// 4,5行已经定义了map和use数据，所以在此处不必int map[n][m],直接map[n][m]即可，否则报错
map[n][m];
use[n][m];
memset(use,,sizeof(use));
int x_start = ;
int y_start = ;
int step = ;
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
cin >> map[i][j];
if(map[i][j] == 'k')
{
x_start = i;
y_start = j;
}
}
}
cout<<x_start<<" "<<y_start<<endl;
dfs(x_start, y_start, step);
cout<<"最小步数"<<minn<<endl;
}
BFS解决如下：
（1）自己写的有缺陷的代码：
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
char map[][];
int vis[][];
int use[][];
int m,n;
int x_start,y_start;
queue<int> que;
int dir[][] = {{,},{,-},{,},{-,}};
int cnt = ;
int mi = ; int pan(int x,int y)
{
if( <= x && x <= n- && <= y && y <= m - &&map[x][y] != '*') return ;
else return ;
} void bfs(int x,int y)
{
int x1 = x;
int y1 = y;
while(!que.empty())
{
vis[x1][y1] = ;
x1 = que.front();
que.pop();
y1 = que.front();
que.pop();
cout<<"x1:"<<x1<<" "<<"y1:"<<y1<<endl;
if(map[x1][y1] == 'e')
{
if(use[x1][y1] == )
{
cnt++;
use[x1][y1]=;
}
continue;
} for(int i = ; i < ; i++)
{
int xx = x1 + dir[i][];
int yy = y1 + dir[i][];
if(pan(xx,yy) && vis[xx][yy] == )
{
cout<<"dd"<<endl;
cout<<xx<<" "<<yy<<endl;
que.push(xx);
que.push(yy);
vis[xx][yy] = ;
}
}
}
} int main()
{
memset(vis,,sizeof(vis));
memset(use,,sizeof(use));
cin >> n >> m;
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
cin >> map[i][j];
if(map[i][j] == 'k')
{
x_start = i;
y_start = j;
}
}
}
que.push(x_start);
que.push(y_start);
bfs(x_start,y_start);
cout<<cnt<<endl; }
对于每个点每个状态我采用的是直接利用队列记录他们的坐标值，而不是如AC代码一样利用结构体记录每个点的每个状态。所以导致我整个程序还是存在很大的缺陷，例如求最短路径的时候就比较困难。
所以对于BFS的题目，强烈建议把每个点每个状态先用结构体表示，然后利用队列记录这些结构体即可。
（2）AC代码
#include<bits/stdc++.h>
using namespace std;
char a[][];
bool usd[][];
int Move[][]={{,},{,},{-,},{,-}};
struct now
{
int x,y,dis;
};
queue<now>q;
int main()
{
int n,m,cnt=;
scanf("%d%d",&n,&m);
now s;
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
{
cin>>a[i][j];
if(a[i][j]=='k')
{
s.x=i;
s.y=j;
s.dis=;
}
}
q.push(s);
int ans=;
while(!q.empty())
{
now Now=q.front();
q.pop();
if(a[Now.x][Now.y]=='e')
{
if(!usd[Now.x][Now.y])
{
++cnt;
ans=min(ans,Now.dis);
}
usd[Now.x][Now.y]=true;
continue; //到达出口"e"处就必须跳过一下步骤，不能在对出口点“e”进行下面的扩展步骤(上下左右)
}
usd[Now.x][Now.y]=true;
for(int i=;i<;++i)
{
int xx=Now.x+Move[i][],yy=Now.y+Move[i][],d=Now.dis;
if(xx<=n&&xx>=&&yy>=&&yy<=m&&!usd[xx][yy]&&a[xx][yy]!='*')
{
now t;
t.x=xx;
t.y=yy;
t.dis=d+;
q.push(t);
}
}
}
if(!cnt)
return !printf("-1\n");
printf("%d %d\n",cnt,ans);
return ;
}
带路径输出的BFS(路径的输出主要依靠递归程序，记录每个点的结构体还需要记录每个点的前驱节点的坐标)
#include<bits/stdc++.h>
using namespace std;
char a[][];
bool usd[][];
int Move[][]={{,},{,},{-,},{,-}};
struct now
{
int x,y,dis,pre_x,pre_y;
};
queue<now>q;
now buf[];
int count1 = ; void print(int x,int y)
{
int temp;
for(int i = ; i < count1; i++)
{
if(buf[i].x == x && buf[i].y == y) temp = i;
}
if(x == - && y == -) return;
else
{
print(buf[temp].pre_x,buf[temp].pre_y);
cout<<"("<<x<<","<<y<<")"<<endl;
}
} int main()
{
int n,m,cnt=;
scanf("%d%d",&n,&m);
now s;
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
{
cin>>a[i][j];
if(a[i][j]=='k')
{
s.x=i;
s.y=j;
s.pre_x = -;
s.pre_y = -;
s.dis=;
}
}
q.push(s);
int ans=;
while(!q.empty())
{
now Now=q.front();
buf[count1++] = Now;
q.pop();
if(a[Now.x][Now.y]=='e')
{
if(!usd[Now.x][Now.y])
{
++cnt;
ans=min(ans,Now.dis);
usd[Now.x][Now.y]=true;
print(Now.x,Now.y);
}
continue;
}
usd[Now.x][Now.y]=true;
for(int i=;i<;++i)
{
int xx=Now.x+Move[i][],yy=Now.y+Move[i][],d=Now.dis;
if(xx<=n&&xx>=&&yy>=&&yy<=m&&!usd[xx][yy]&&a[xx][yy]!='*')
{
now t;
t.x=xx;
t.y=yy;
t.pre_x = Now.x;
t.pre_y = Now.y;
t.dis=d+;
q.push(t);
}
}
}
if(!cnt)
return !printf("-1\n");
printf("%d %d\n",cnt,ans);
// for(int i = 0; i < count1; i++)
// {
// cout<<buf[i].x<<" "<<buf[i].y<<" "<<buf[i].pre_x<<" "<<buf[i].pre_y<<endl;
// }
return ;
}
利用dfs解决最大连通块问题！
题目描述
农场主约翰的农场在最近的一场风暴中被洪水淹没，这一事实只因他的奶牛极度害怕水的消息而恶化。
然而，他的保险公司只会根据他农场最大的“湖”的大小来偿还他一笔钱。
农场表示为一个矩形网格，有N（1≤N≤100）行和M（1≤M≤100）列。网格中的每个格子要么是干的，
要么是被淹没的，而恰好有K（1≤K≤N×M）个格子是被淹没的。正如人们所期望的，一个“湖”有一个
中心格子，其他格子通过共享一条边（只有四个方向，对角线不算的意思）与之相连。任何与*格子共享一条边或与*格
子相连的格子共享一条边的格子都将成为湖的一部分。
输入描述:
第一行有三个整数N,M,K，分别表示这个矩形网格有N行，M列，K个被淹没的格子。 接下来K行，每一行有两个整数R,C。表示被淹没的格子在第R行，第C列。
输出描述:
输出最大的“湖”所包含的格子数目
输入
3 4 5
3 2
2 2
3 1
2 3
1 1
输出
4
#include<iostream>
using namespace std;
int map[][];
int vis[][] = {};
int used[][] = {};
int dir[][] = {{,},{-,},{,},{,-}};
int n,m,k;
int cnt = ;
int maxx = -;
int pan(int x,int y)
{
if(map[x][y] == && <= x && x <= n- && y <= m- && y >= && vis[x][y] == && used[x][y]==)
{
return ;
}
else return ;
} void dfs(int x,int y,int c) //连通块问题就不像迷宫问题有递归出口！！！！
{
vis[x][y] = ;
// cout<<x<<" "<<y<<" dd"<<endl;
for(int i = ; i < ; i++)
{
int xx = x + dir[i][];
int yy = y + dir[i][];
if(pan(xx,yy))
{
// cout<<xx<<" "<<yy<<endl;
vis[xx][yy] = ;
used[xx][yy] = ; // used数组是防止多次记录连通块！
cnt++;
c = cnt; // 这一块必须注意，不能直接传入cnt，因为递归函数是放在栈中，倘若传入cnt，递归函数出栈时，cnt的值也会变化，所以用c代替cnt.
dfs(xx,yy,c);
vis[xx][yy] = ;
}
}
} int main()
{
cin >> n >> m >> k;
map[n][m];
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++) map[i][j] = ;
}
for(int i = ; i < k; i++)
{
int x,y;
cin >> x >> y;
map[x-][y-] = ;
}
// for(int i = 0; i < n; i++) 打印整个地图
// {
// for(int j = 0; j < m; j++)
// {
// cout<<map[i][j];
// }
// cout<<endl;
// }
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
cnt = ;
if(map[i][j] == )
{
dfs(i,j,cnt);
if(cnt > maxx) maxx = cnt;
}
}
}
cout<<maxx<<endl; }
本题总结：
1.利用dfs解决连通块问题与利用dfs解决迷宫问题存在一定的区别：
（1）迷宫问题有固定的入口或者出口，而连通块问题就没有所谓的出口或者入口，它需要遍历map[][]数组中的每个元素！