【多维BFS】ABC311 D

Dear 丶 2024-03-22 19:58 86阅读 0赞

[D - Grid Ice Floor][]

题意：

![21929a903e384fb5ba0355f5a95a8438.png][]

思路：

可以发现，这种魔改BFS和dij的题，一般都是改两个部分：转移和边权

这个BFS魔改转移，就是遇到\#时打转找到合适的方向即可

转移时分类讨论即可

Code：

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=1e3+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    string s[mxn];
    
    int N,M;
    int vis[mxn][mxn][4];
    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
    
    bool check(int x,int y){
    	return x>=1&&x<=N&&y>=1&&y<=M;
    }
    void solve(){
    	cin>>N>>M;
    	for(int i=1;i<=N;i++){
    		cin>>s[i];
    		s[i]=" "+s[i];
    	}
    	queue<array<int,3> > Q;
    	for(int i=0;i<4;i++){
    		vis[2][2][i]=1;
    		Q.push({2,2,i});
    	}
    	while(!Q.empty()){
    		auto [x,y,d]=Q.front();
    		Q.pop();
    		int vx=x+dx[d];
    		int vy=y+dy[d];
    		if(s[vx][vy]=='#'){
    			for(int i=0;i<4;i++){
    				if(i==d) continue;
    				if(vis[x][y][i]) continue;
    				vis[x][y][i]=1;
    				Q.push({x,y,i});
    			}
    		}else{
    			if(vis[vx][vy][d]) continue;
    			vis[vx][vy][d]=1;
    			Q.push({vx,vy,d});
    		}
    	}
    	int ans=0;
    	for(int i=1;i<=N;i++){
    		for(int j=1;j<=M;j++){
    			int ok=0;
    			for(int k=0;k<4;k++){
    				ok|=vis[i][j][k];
    			}
    			if(ok) ans++;
    		}
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[D - Grid Ice Floor]: https://atcoder.jp/contests/abc311/tasks/abc311_d
[21929a903e384fb5ba0355f5a95a8438.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/6b834575d1c4494d990c49ebd59a6018.png