题解 | #地牢逃脱#BFS思路 计数

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    int n, m;
    while(cin >> n >> m)
    {
        char c1;
        vector<vector<int>> matrix(n,vector<int>(m));
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                cin >> c1;
                if(c1 == '.')
                {
                    matrix[i][j] = 0;
                    sum ++;
                }
                else
                {
                    matrix[i][j] = 1;
                }
                    
            }
        }
        //cout << " sum = " << sum << endl;
        int x0, y0;
        cin >> x0 >> y0;
        int k;
        cin >> k;
        vector<vector<int>> dir(k,vector<int>(2));
        for(int i = 0; i < k; i++)
        {
            int dx, dy;
            cin >> dx >> dy;
            dir[i] = {dx,dy};
        }
        queue<pair<int,int>> q;
        queue<int> lvs;
        q.push({x0,y0});
        lvs.push(0);
        int level = 0;
        sum --;
        matrix[x0][y0] = 1;
        while(!q.empty())
        {
            auto [curr_x,curr_y] = q.front();
            q.pop();
            level = lvs.front();
            lvs.pop();
            for(int i = 0; i < k; i++)
            {
                int next_x, next_y; 
                next_x = curr_x + dir[i][0];
                next_y = curr_y + dir[i][1];
                if(next_x >= 0 && next_x < n && next_y>=0 && next_y < m && matrix[next_x][next_y] == 0)
                {
                    q.push({next_x,next_y});
                    lvs.push(level+1);
                    matrix[next_x][next_y] = 1;
                    sum--;
                }
                
            }
            
            
        }
        //cout << "result sum " << sum << endl;
        if(sum > 0) level = -1;
        cout << level << endl;
        
    }
}