BFS的思想主要就是一层层扩散出去,使用一个辅助队列来实现,简单来讲就是每一步都要走可以走(判定边界,没走过等)的四个方向。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
char mpt[maxn][maxn];
int vis[maxn][maxn];
int dir[4][2] = {0,1,1,0,-1,0,0,-1};
struct node{
int x,y;
int step;
};
int bfs(int sx,int sy){
memset(vis,0, sizeof(vis));
queue<node> q;
q.push(node{sx,sy,0});
vis[sx][sy] = 1;
int ans = 0;
while (!q.empty()){
node now = q.front();
q.pop();
if(mpt[now.x][now.y] == 'E'){
ans = now.step;
break;
}
for(int i = 0;i < 4;i++){
int nx = now.x + dir[i][0];
int ny = now.y + dir[i][1];
if((mpt[nx][ny] == '*'||mpt[nx][ny] == 'E')&&vis[nx][ny] == 0){
q.push(node{nx,ny,now.step+1});
vis[nx][ny] = 1;
}
}
}
return ans;
}
int main(){
int h,w;
while (cin>>h>>w){
int sx,sy;
for(int i = 1;i <= h;i++){
cin>>mpt[i]+1;
for(int j = 1;j <= w;j++){
if(mpt[i][j] == 'S')
sx = i, sy = j;
}
}
int ans = bfs(sx,sy);
cout<<ans<<endl;
}
return 0;
}
DFS,简单来说就是一条路走到底,走不通的时候回溯回来再走另一个方向,要注意回溯的时候要把走过的路标记为没走
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
char mpt[maxn][maxn];
int vis[maxn][maxn];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int ans;
void dfs(int x,int y,int step){
if(step >= ans)return;//步数超过之前记录最短的就不用继续
if(mpt[x][y] == 'E'){
ans = min(ans,step);
return;
}
for(int i = 0;i < 4;i++){
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if((mpt[nx][ny] == '*' || mpt[nx][ny] == 'E')&& vis[nx][ny] == 0){
vis[nx][ny] = 1;
dfs(nx,ny,step+1);
vis[nx][ny] = 0;//回溯的时候标记为未走
}
}
}
int main(){
int h,w;
while (cin>>h>>w){
if(h == 0 && w == 0)
break;
int sx = 0,sy = 0;
memset(mpt,0, sizeof(mpt));
memset(vis,0, sizeof(vis));
for(int i = 1;i <= h;i++){
cin>>mpt[i] + 1;
for(int j = 1;j <= w;j++){
if(mpt[i][j] == 'S')
sx = i, sy = j;
}
}
ans = 999999;
dfs(sx,sy,0);
cout<<ans<<endl;
}
return 0;
}