bfs求助
查看原帖
bfs求助
152652
AndyChen2005121楼主2020/10/26 18:15
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
char a[105][105];
bool vis[105][105];
int cnt[105][105];
int n, m;
const int inf = 0x3f3f3f3f;
int st1=0, st2=0, st3=0, st4=0;
bool in(int x, int y){
    return x >= 0 && x < m && y >= 0 && y < n;
}
int pos[4][2] = {0,-1,-1,0, 0,1,1,0};
struct node{
    int x, y, d;
    node(int xx, int yy, int dd){
        x = xx;
        y = yy;
        d = dd;
    }
};
queue<node> q;
void dfs(int k, node now){
    if(cnt[now.x][now.y]<now.d || cnt[now.x][now.y]==inf) return;
    if(!in(now.x, now.y)) return;
    cnt[now.x][now.y]=now.d;
    q.push(node(now.x,now.y,now.d));
    dfs(k, node(now.x+pos[k][0], now.y+pos[k][1], now.d)); 
}
int bfs(int x, int y){
    q.push(node(x,y, -1));
    vis[x][y] = true;
    while(!q.empty()){
        node now = q.front();
        q.pop();
        now.d++;
        for(int k = 0; k < 4; k++){
            node v=now;
            v.x = now.x + pos[k][0], v.y = now.y + pos[k][1];
            dfs(k, v);
        }
    }
}
int main(){
    cin >> n >> m;
    memset(cnt,inf-1,sizeof(cnt));
    bool flag=false;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
            if(a[i][j] == 'C'){
                if(!flag){st1=i; st2=j; flag=true;}
                else {st3=i; st4=j;}
            }
            if(a[i][j] == '*') cnt[i][j]=inf;
        }
    }
    bfs(st1, st2);
    cout << cnt[st1][st2] << endl;

    return 0;
}
2020/10/26 18:15
加载中...