题解 | #拜访#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型vector<vector<>> 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    int countPath(vector<vector<int> >& g, int n, int m) {
        vector<vector<bool>> st(n+1,vector<bool>(m+1,false));
        vector<vector<int>> dis(n+1,vector<int>(m+1,-1));

        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        queue<pair<int,int>> q;
        int ex,ey;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(g[i][j]==1)
                {
                    q.push({i,j});
                    dp[i][j]=1;
                    dis[i][j]=0; 
                    st[i][j]=true;
                }
                else if(g[i][j]==2)ex=i,ey=j;
                else if(g[i][j]==-1)st[i][j]=true;
            }
        }


        while(q.size())
        {
            int c=q.size();

            for(int i=1;i<=c;i++)
            {
                auto [x,y]=q.front();
                q.pop();
                for(int k=0;k<4;k++)
                {
                    st[x][y]=true;
                    int px =x+dx[k],py=y+dy[k];
                    if(px>=0&&px<n&&py>=0&&py<m&&!st[px][py])
                    {
                        if(dis[px][py]==-1)//只有第一次遍历到该点的时候才会把px,py加入队列
                        {
                            q.push({px,py});
                            dis[px][py]=dis[x][y]+1;
                            dp[px][py]+=dp[x][y];
                        }
                        else {
                            if(dis[px][py]==dis[x][y]+1)
                            {
                                dp[px][py]+=dp[x][y];
                            }

                        }
                    }
                }
                
            }   
        }
        return dp[ex][ey];

        
    }
};