题目链接

题目描述
给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x0 , y0 ) 位置出发，遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 55;
char map[maxn][maxn];
int vis[maxn][maxn];
int dir[maxn][2];
struct node{
    int x;
    int y;
    int step;
};
int n,m,cnt;
int flag;
int k;
int bfs(int x,int y)
{
    node temp;
    temp.x=x;
    temp.y=y;
    temp.step=0;
    queue<node> q;
    q.push(temp);
  //     cout<<cnt<<"    "<<endl;
    while(!q.empty())
    {
 
        node t;
        t=q.front();
        q.pop();
        int tx,ty,tstep;
        tx=t.x;
        ty=t.y; 
        tstep=(t.step)+1;
        //cout<<tx<<" "<<ty<<"  step:"<<t.step<<endl;
        int nx,ny,nstep;
        //cout<<k<<endl;
        for(int i=0;i<k;++i)
        {
            int nx = tx + dir[i][0];
            int ny = ty + dir[i][1];
            //cout<<nx<<" "<<ny<<endl;
            if(nx<0 || ny<0 || nx>=n || ny>=m || vis[nx][ny] || map[nx][ny]=='X')
            //if(nx<0 || ny<0 || nx>=n || ny>=m || vis[nx][ny] )
            {
                continue;    
            }    
            
//            int flag=1;
//            if(nx==tx)
//            {
//                int a = max(ny,ty);
//                int b = min(ny,ty);
//                for(int i=b+1;i<=a;++i)
//                {
//                    if(map[nx][i]=='X')
//                    {
//                        flag=0;
//                        break;
//                    }
//                }
//            }else if(ny==ty)
//            {
//                int a = max(nx,tx);
//                int b = min(nx,tx);
//                for(int i=b+1;i<=a;++i)
//                {
//                    if(map[nx][i]=='X')
//                    {
//                        flag=0;
//                        break;
//                    }
//                }                
//            }
//            if(flag==0)
//            {
//                continue;
//            }
            vis[nx][ny]=1;
            //cout<<nx<<" "<<ny<<endl;
            cnt--;
            //cout<<"this"<<endl;
            if(cnt==0)
            {
                //cout<<"end"<<endl;
                return tstep;
            }
            node ttt;
            ttt.x=nx;
            ttt.y=ny;
            ttt.step=tstep;
            
            //cout<<nx<<" "<<ny<<" "<<tstep<<endl;
            q.push(ttt);
        }
        //system("pause");
    }
    return -1;
}
int main()
{
    //int n,m;                    //n行m列 
    while(cin>>n>>m)
    {
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;++i)
        {
            scanf("%s",map+i);
        }
        int x,y;        //牛牛的起点坐标
        cin>>x>>y;
        //int k;            //合法步长数
        cin>>k;
        for(int i=0;i<k;++i)
        {
            cin>>dir[i][0]>>dir[i][1];
        }
        vis[x][y]=1;
        cnt = -1;
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                if(map[i][j]=='.')
                {
                    cnt++;
                }
            }
        }
        flag=0;
        cout<<bfs(x,y)<<endl;
    }
    return 0;
}