bfs+dfs
=是的你没看错=:
就是bfs+dfs同时写,因为太蠢了,想不到什么好办法
1.因为只有两块斑点,所以我们先用dfs把一块写为A,另一块写为B
2.把为A的点放入队列中去,并且标记为true
3.然后正常的bfs搜索第一个到达B的点的距离就是答案
还是代码香香:
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
char mp[N][N];
bool vis[N][N];
int n,m;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
struct node{
int x,y,step;
node(int cx,int cy,int cs){
x=cx,y=cy,step=cs;
}
};
queue<node>q;
void bfs()//bfs板子
{
while(!q.empty()){
node t = q.front();
q.pop();
if(mp[t.x][t.y]=='B') {
cout<<t.step-1<<endl; //减一是因为到了B之后会多加一步
return;
}
for(int i = 0;i < 4;i ++ ){
int xx = t.x + dx[i],yy = t.y + dy[i];
if(!vis[xx][yy] && xx>=1 && yy>=1 && xx<=n && yy<=m){
vis[xx][yy] = true;
q.push(node(xx,yy,t.step+1));
}
}
}
}
void dfs(int x,int y,char op)//dfs板子
{
mp[x][y]=op;
for(int i = 0;i < 4;i ++ ){
int xx = x + dx[i];
int yy = y + dy[i];
if(mp[xx][yy]=='X' && xx<=n && xx>=1 && yy>=1 && yy <= m)
dfs(xx,yy,op);
}
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n; i++ ) //正常的读图
for(int j = 1;j <= m;j ++ )
cin >> mp[i][j];
int cnt = 0;
for(int i = 1;i <= n; i++ )
for(int j = 1;j <= m;j ++ ){
if(mp[i][j] == 'X' && cnt == 0) { //因为有两快斑点,所以这里用cnt表示每一块
dfs(i,j,'A');cnt ++ ; //cnt为0,把该块全部X改为A
}
if(mp[i][j] == 'X' && cnt == 1) dfs(i,j,'B');//cnt为1把该块全部X改为B
}
for(int i = 1;i <= n; i++ )
for(int j = 1;j <= m;j ++ )
if(mp[i][j]=='A') {
q.push(node(i,j,0));//将所有A放入队列
vis[i][j] = true; //标记所有A
}
bfs();//搜索
return 0;
}
好了,妥妥的板子题