官方题解

题目大意

有一个 $n\times m$ 的迷宫，每个格子有一种颜色，每种颜色代表一种移动方向，最多改变 $k$ 个格子的颜色，判断能否从 $(1,1)$ 移动到 $(n,m)$ 。

解题思路

考虑每个格子的上下左右四个移动方向，可以对相邻格子都建有向边，若当前格子地板的移动方向与要移动的方向相同，建一条边权为 $0$ 的有向边，若方向不同，建一条边权为 $1$ 的有向边。

于是问题就转化为了最短路问题，求出从 $(1,1)$ 到达 $(n,m)$ 需要花费的最小代价，若比 $k$ 大，则无法逃离迷宫，否则，可以逃离迷宫。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9+10;

struct P{
    int dis;
    int x,y;

    bool operator<(const P& b) const {
        return dis>b.dis;
    }
};

map<char,int>dir;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void solve(){
    int n,m,k;cin>>n>>m>>k;
    vector<vector<char>>g(n+1,vector<char>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
        }
    }

    priority_queue<P>q;
    vector<vector<bool>>vis(n+1,vector<bool>(m+1));
    vector<vector<int>>d(n+1,vector<int>(m+1,INF));
    d[1][1]=0;
    q.push({0,1,1});
    while(!q.empty()){
        auto [dis,x,y]=q.top();
        q.pop();

        if(vis[x][y]) continue;
        vis[x][y]=true;

        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m) continue;

            if(dir[g[x][y]]==i){
                if(d[nx][ny]>d[x][y]){
                    d[nx][ny]=d[x][y];
                    q.push({d[nx][ny],nx,ny});
                }
            }
            else{
                if(d[nx][ny]>d[x][y]+1){
                    d[nx][ny]=d[x][y]+1;
                    q.push({d[nx][ny],nx,ny});
                }
            }
        }
    }

    if(d[n][m]>k) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}

int main(){
    dir['O']=0;dir['G']=1;dir['B']=2;dir['Y']=3;
    int T=1;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}