题解 | #地牢逃脱#

#include<vector>
#include<iostream>
#include<queue>
using namespace std;

struct step
{
    int x;
    int y;
    int level;//表示这“步”需要从起始点走多少level步，而不一定是最少多少步，由遍历决定
};

//解决给定了障碍物和通路的地图上，
//求给定多个每次移动的向量后，到达终点（未定）所需最多的最少步数
//（比如你左边如果是通路就可能是终点，但如果终点可能在更远步数的地方，左边就不是所求）
//如果把所有的情况都走完了，发现仍然有不可达到的地方，那么如果那里是终点，即终点不可哒，返回-1
int main(void)
{
    int n,m;
    while(cin>>n>>m)
    {
    //记录地图，X表示障碍物，.表示可以走，走到.之后需要把.改为X，标记已经走过
    vector<vector<char> > vs(n,vector<char>(m));//可以考虑用二维int优化
    
    //记录有多少个点可以走，每走一次就--，最后遍历完成如果还>0说明有没有走到的step，返回-1
    int sum=0;
    
    
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            cin>>vs[i][j];
            
            if(vs[i][j]=='.')
                sum++;
        }
    
    int x0,y0;
        
    step s0;
    cin>>s0.x>>s0.y;
    s0.level = 0;
    queue<step> qp;
    qp.push(s0);
    sum--;//走起始点，sum--
    vs[s0.x][s0.y] = 'X'; //走过该格，将'.'改成 'X'
        
    int k;
    cin>>k;
        
    vector<pair<int,int> >vp;//记录允许每步走的情况
    
    for(int i=0;i<k;i++)
    {
        int x_,y_;
        cin>>x_>>y_;
        vp.push_back({x_,y_});
    }
    
    int level = 0;
        
    while(!qp.empty())
    {
        auto tmp = qp.front();
        qp.pop();
        
        level = tmp.level;
        
        for(int i=0;i<k;i++)
        {
            int next_x = tmp.x + vp[i].first;
            int next_y = tmp.y + vp[i].second;
            //假设走了这一步
			
            //这一步可以走
            if(next_x>=0&&next_y>=0&&next_x<n&&next_y<m&&vs[next_x][next_y]=='.')
            {
            
            //记录已经走过格子所做的操作，见出生点注释
                sum--;
                vs[next_x][next_y]='X';
            
            //或考虑对取出的tmp操作
            //将该步的情况加入队列进行下一次遍历
                step temp;
                temp.x = next_x;
                temp.y = next_y;
                temp.level = level+1;
                qp.push(temp);
            }
        }
    }
    
    if(sum>0) level=-1;
    cout<<level<<endl;
}
    return 0;
}