bfs

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=310;
char g[N][N];
int dist[N][N];
int m,n;
typedef pair<int,int>PII;
#define x first
#define y second


int bfs(int sstart,int eend)
{
    memset(dist,-1,sizeof dist);
    dist[sstart][eend]=0;

    queue<PII>q;//需要放到方法中

    q.push({sstart,eend});
    int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0};
    while(q.size())
    {
        PII temp=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int a=temp.x+dx[i],b=temp.y+dy[i];
            if(g[a][b]=='*')return dist[temp.x][temp.y]+1;
            if(dist[a][b]!=-1)continue;
            if(g[a][b]!='.')continue;
            if(a<0 && a>=m && b<0 && b>=n)continue;

            dist[a][b]=dist[temp.x][temp.y]+1;
            q.push({a,b});

        }
    }
    return -1;
}

int main()
{
    while(cin>>m>>n)
    {
        if(m==0&&n==0)return 0;
        memset(g,' ',sizeof g);
        for(int i=0;i<m;i++)
            scanf("%s",g[i]);
        int sstart=0,eend=0;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(g[i][j]=='@')
                {
                    sstart=i;
                    eend=j;
                }
        cout<<bfs(sstart,eend)<<endl;    
    }
}