68pts求调
查看原帖
68pts求调
760998
rhn7楼主2024/7/30 19:23
#include<bits/stdc++.h>
using namespace std;
int n,m,D[2500005];
int cal(int x,int y){return (x-1)*(m+1)+y;}
char ch;
vector<pair<int,int> > G[2500005];
deque<int> q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ch;
			G[cal(i,j)].push_back({cal(i+1,j+1),(ch!='\\')});
			G[cal(i+1,j+1)].push_back({cal(i,j),(ch!='\\')});
			G[cal(i+1,j)].push_back({cal(i,j+1),(ch!='/')});
			G[cal(i,j+1)].push_back({cal(i+1,j),(ch!='/')});
		}
	}
	memset(D,0x3f,sizeof(D));
	q.push_back(1);D[1]=0;
	while(!q.empty()){
		int x=q.front();q.pop_front();
		for(auto [y,w]:G[x]){
			if(D[y]>1e9){
				D[y]=D[x]+w;
				if(w) q.push_back(y);
				else q.push_front(y);
			}
		}
	}
    if(D[(n+1)*(m+1)]>1e9) cout<<"NO SOLUTION";
	else cout<<D[(n+1)*(m+1)];
	return 0;
}
2024/7/30 19:23
加载中...