68分悬关求调,只有红绿
查看原帖
68分悬关求调,只有红绿
1180231
H_dream楼主2024/9/7 22:24
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=510;
int n,m;
char a[N][N];
bool vis[N][N];
int d1[4][2]={-1,-1,-1,1,1,-1,1,1};
int d2[4][2]={-1,-1,-1,0,0,-1,0,0};
struct node{
	int x,y,ans;
};
bool operator <(const node &a,const node &b){
	return a.ans>b.ans;
}
int bfs(){
	priority_queue<node> q;
	vis[0][0]=1;
	q.push({0,0,0});
	while(!q.empty()){
		int x=q.top().x;
		int y=q.top().y;
		int ans=q.top().ans;
		q.pop();
		//cout<<x<<' '<<y<<' '<<ans<<endl;
		if(x==n&&y==m) return ans;
		for(int i=0;i<4;++i){
			int xx=x+d1[i][0];
			int yy=y+d1[i][1];
			if(xx<0||xx>n||yy<0||yy>m) continue;
			if(vis[xx][yy]) continue;
			vis[xx][yy]=1;
			char t=a[x+d2[i][0]][y+d2[i][1]];
			if(t=='\\'){
				if(i==0||i==3)
					q.push({xx,yy,ans});
				else
					q.push({xx,yy,ans+1});
			}
			else {
				if(i==1||i==2)
					q.push({xx,yy,ans});
				else
					q.push({xx,yy,ans+1});
			}
			//cout<<xx<<' '<<yy<<' '<<x+h<<' '<<y+l<<' '<<t<<endl;
		}
	}
	return 0;
}
signed main(){
	cin>>n>>m;
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			cin>>a[i][j];
	if(n+m&1==1) cout<<"NO SOLUTION";
	else cout<<bfs();
	
	return 0;
}
2024/9/7 22:24
加载中...