【分层图BFS】AB路线

朴灿烈づ我的快乐病毒、 2024-03-17 15:33 49阅读 0赞

[P2038 - AB 路线 - ZJHUOJ][P2038 - AB _ - ZJHUOJ]

题意：

![54e2a858635f4c02a86ca091d9727431.png][]

![a82add89a77f4ab39b892802e1292928.png][]

思路：

首先看是什么影响了决策，即能不能走这个格子

走到当前格子是第几步和格子的字符种类影响了能不能走该格子，因此需要多加一维k，表示走到当前字符种类的第k步

然后就可以去BFS了，但是每个状态可能会重复遍历，我们要求的是最少步数，怎么办

可以用一个类似与最短路的办法，记录一个DP数组，然后松弛

最后在统计答案的时候记得枚举一下这是以第几步到达的终点

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=1e3+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    queue<array<int,4> > Q;
    //dis,x,y,k
    //距离，横坐标，纵坐标，该字符走了几步
    
    string s[mxn];
    
    int N,M,K;
    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
    int dp[mxn][mxn][12];
    int a[mxn][mxn];
    
    bool check(int x,int y){
    	return x>=1&&x<=N&&y>=1&&y<=M;
    }
    void bfs(){
    	memset(dp,0x3f,sizeof(dp));
    	dp[1][1][1]=0;
    	Q.push({0,1,1,1});
    	while(!Q.empty()){
    		auto it=Q.front();
    		Q.pop();
    		for(int i=0;i<4;i++){
    			int x=it[1],y=it[2],k=it[3];
    			int dis=it[0];
    			int vx=x+dx[i];
    			int vy=y+dy[i];
    			int vk=k+1;
    			if(check(vx,vy)){
    				if(a[vx][vy]==a[x][y]){
    					if(vk==K+1) continue;
    					if(dp[vx][vy][vk]>dis+1){
    						dp[vx][vy][vk]=dis+1;
    						Q.push({dis+1,vx,vy,vk});
    					}
    				}else{
    					if(vk!=K+1) continue;
    					if(dp[vx][vy][1]>dis+1){
    						dp[vx][vy][1]=dis+1;
    						Q.push({dis+1,vx,vy,1});
    					}
    				}
    			}
    		}
    	}
    }
    void solve(){
    	cin>>N>>M>>K;
    	for(int i=1;i<=N;i++){
    		cin>>s[i];
    		s[i]=" "+s[i];
    	}
    	for(int i=1;i<=N;i++){
    		for(int j=1;j<=M;j++){
    			if(s[i][j]=='A') a[i][j]=1;
    			else a[i][j]=0;
    		}
    	}
    	bfs();
    	int mi=1e9;
    	for(int i=1;i<=K;i++) mi=min(mi,dp[N][M][i]);
    	if(mi==1e9) cout<<-1<<'\n';
    	else cout<<mi<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[P2038 - AB _ - ZJHUOJ]: http://172.20.8.83/problem.php?id=2038
[54e2a858635f4c02a86ca091d9727431.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/def5f1827d82437685ecd41edc066cf9.png
[a82add89a77f4ab39b892802e1292928.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/1b3b431353de4000a326214c7f1d31ab.png