30pts,Help
查看原帖
30pts,Help
1191031
majingxuan123楼主2024/8/29 16:11
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
int n,m;
int a[505][505];
int d[505][505];
int dx[4]={-1,1,1,-1};
int dy[4]={-1,1,-1,1};
int bfs(){
	deque<PII> q;
	q.push_back({0,0});
	memset(d,-1,sizeof d);
	d[0][0]=0;
	while(!q.empty()){
		PII t=q.front();
		q.pop_front();
		int tx=t.first,ty=t.second;
		for(int i=0;i<4;i++){
			int fx=dx[i]+tx;
			int fy=dy[i]+ty;
			if(fx>=0&&fx<=n&&fy>=0&&fy<=m&&d[fx][fy]==-1){
				if(i<2){
					if(a[fx][fy]==1)q.push_back({fx,fy}),d[fx][fy]=d[tx][ty]+1;
					else q.push_front({fx,fy}),d[fx][fy]=d[tx][ty];
				}
				else{
					if(a[fx][fy]==2)q.push_back({fx,fy}),d[fx][fy]=d[tx][ty];
					else q.push_front({fx,fy}),d[fx][fy]=d[tx][ty]+1;
				}
			}
		}
	}
	return d[n][m];
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char ch;
			cin>>ch;
			if(ch=='/')a[i][j]=1;
			else a[i][j]=2;
		}
	}
	if((n+m)%2)cout<<"NO SOLUTION";
	else cout<<bfs();
	return 0;
}
2024/8/29 16:11
加载中...