40pts 玄关 求救 wa
查看原帖
40pts 玄关 求救 wa
778070
tall_buildin楼主2025/1/26 19:16
#include <bits/stdc++.h>
using namespace std;
int n,m;
int ans = -1;
int d[5] = {0,1,2,3,4};//1:东 2:南 3:西 4:北;
struct boat{
	int x,y;
	int p;
	int t;
};
boat qsd,zd; 
bool a[55][55];
bool vis[55][55];
void bfs(){
	queue<boat>q;
	vis[qsd.x][qsd.y] = 1;
	q.push(qsd);
	while(!q.empty()){
		boat temp = q.front();
		q.pop();
		if (temp.x == zd.x && temp.y == zd.y){
			ans = temp.t;
			return;
		}
		boat tmp = temp;
		for (int i = 1;i<=3;i++){
			//东;
			if (abs(tmp.p-1)<3)	tmp.t+=abs(tmp.p-1);
			else tmp.t+=1;
			tmp.x+=i;
			if (tmp.x<m&&tmp.x>1&&tmp.y<n&&tmp.y>1&&vis[tmp.x][tmp.y] == 0&&a[tmp.x][tmp.y] == 0){
				tmp.t+=i;
				vis[tmp.x][tmp.y] = 1; 
				q.push(tmp);
			}
			//南;
			tmp = temp;
			if (abs(tmp.p-2)<3)	tmp.t+=abs(tmp.p-2);
			else tmp.t+=1;
			tmp.y+=i;
			if (tmp.x<m&&tmp.x>1&&tmp.y<n&&tmp.y>1&&vis[tmp.x][tmp.y] == 0&&a[tmp.x][tmp.y] == 0){
				tmp.t+=i;
				vis[tmp.x][tmp.y] = 1; 	
				q.push(tmp);
			}
			//西;
			tmp = temp;
			if (abs(tmp.p-3)<3)	tmp.t+=abs(tmp.p-3);
			else tmp.t+=1;
			tmp.x-=i;
			if (tmp.x<m&&tmp.x>1&&tmp.y<n&&tmp.y>1&&vis[tmp.x][tmp.y] == 0&&a[tmp.x][tmp.y] == 0){
				tmp.t+=i;	
				vis[tmp.x][tmp.y] = 1; 
				q.push(tmp);
			}
			//北;
			tmp = temp;
			if (abs(tmp.p-4)<3)	tmp.t+=abs(tmp.p-4);
			else tmp.t+=1;
			tmp.y-=i;
			if (tmp.x<m&&tmp.x>1&&tmp.y<n&&tmp.y>1&&vis[tmp.x][tmp.y] == 0&&a[tmp.x][tmp.y] == 0){
				tmp.t+=i;	
				vis[tmp.x][tmp.y] = 1; 
				q.push(tmp);
			}
		}
	}
}
int main(){
	memset(a,0,sizeof(a));
	cin>>n>>m;
	for (int i = 1;i<=n;i++)
		for (int j = 1;j<=m;j++){
			cin>>a[i][j];
			if (a[i][j] == 1){
				a[i-1][j] = 1;
				a[i-1][j-1] = 1;
				a[i][j-1] = 1;
			}
		}
	char p;
	cin>>qsd.x>>qsd.y>>zd.x>>zd.y>>p;
	if (p == 'E')	qsd.p = 1;
	if (p == 'S')	qsd.p = 2;
	if (p == 'W')	qsd.p = 3;
	if (p == 'N')   qsd.p = 4;	
	qsd.t = 0;
	bfs();
	cout<<ans;
	return 0;
}

2025/1/26 19:16
加载中...