神殿

題目大意

用一個 n ∗ m n∗m n∗m的矩陣，矩陣的每一個點都是一個房間，房間隻有某些方向有門（見上圖），要從一個房間走向相鄰的房間必須要他們中間的兩個門都是存在，也可以把所有房間的門順時針旋轉一輪。

走到相鄰的房間要一個機關時間，旋轉房間門也要一個時間機關。

現在問從 ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​)走到 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​)最少需要多少各機關時間。

樣例輸入1

2 2
+*
*U
1 1 2 2
           

樣例輸出1

樣例輸入2

2 3
<><
><>
1 1 2 1
           

樣例輸出2

資料範圍

思路

這道題我們用 b f s bfs bfs來做。

其實就是分為走到旁邊的房間和旋轉兩種，具體看代碼吧。

代碼

#include<cstdio>
#include<queue>
using namespace std;
int n,m,x1,y1,x2,y2,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool a[1501][1501][5],in[1501][1501][5];
char c;
struct note
{
	int x,y,t,turn;
};
int abs(int x)
{
	while (x<0) x=4+x;
	return x;
}
void bfs()//bfs
{
	queue<note>l;//建隊列
	l.push((note){x1,y1,0,0});//加入隊列
	in[x1][y1][0]=1;//标記
	if (x1==x2&&y1==y2)//有沒有到終點
	{
		printf("0");//輸出
		return ;//找到終點就可以退出了
	}
	while (l.size())
	{
		note x=l.front();//取出
		l.pop();//用完就可以扔掉了
		for (int i=0;i<4;i++)//枚舉每一個走的方向
		 if (!in[x.x+dx[i]][x.y+dy[i]][x.turn])//是否沒有走過
		  if (a[x.x][x.y][abs(i-x.turn)%4]&&a[x.x+dx[i]][x.y+dy[i]][abs(i-x.turn+2)%4])//是否中間的兩個門都存在
		   if(x.x+dx[i]>0&&x.x+dx[i]<=n&&x.y+dy[i]>0&&x.y+dy[i]<=m)//是否超界
			{
		 		note y;
		 		y.x=x.x+dx[i];//走到那個房間
		 		y.y=x.y+dy[i];
		 		y.t=x.t+1;//所需時間+1
		 		y.turn=x.turn;//房間轉的次數不變
		 		in[y.x][y.y][y.turn]=1;//标記
		 		l.push(y);//加入隊列
		 		if (y.x==x2&&y.y==y2)//是否到了終點
		 		{
		 			printf("%d",y.t);//輸出
		 			return ;//找到終點就可以退出了
				}
			}
		if (!in[x.x][x.y][(x.turn+1)%4])//旋轉
		{
			note y;
			y.x=x.x;//房間不變
			y.y=x.y;
			y.t=x.t+1;//所需時間+1
			y.turn=(x.turn+1)%4;//房間轉的次數+1
			in[y.x][y.y][y.turn]=1;//标記
		 	l.push(y);//加入隊列
		 	if (y.x==x2&&y.y==y2)//是否到了終點
		 	{
		 		printf("%d",y.t);//輸出
		 		return ;//找到終點就可以退出了
			}
		}
	}
	printf("-1");//如果沒有到就退出了，那麼就說明找不到，輸出-1
}
int main()
{
//	freopen("temple.in","r",stdin);
//	freopen("temple.out","w",stdout);
	scanf("%d%d",&n,&m);//讀入
	for (int i=1;i<=n;i++)
	{
		getchar();//處理換行符
		for (int j=1;j<=m;j++)
		{
			c=getchar();//讀入
			if (c=='+')//打表
			{
				a[i][j][0]=1;
				a[i][j][1]=1;
				a[i][j][2]=1;
				a[i][j][3]=1;
			}
			else if (c=='-')//打表
			{
				a[i][j][1]=1;
				a[i][j][3]=1;
			}
			else if (c=='|')//打表
			{
				a[i][j][0]=1;
				a[i][j][2]=1;
			}
			else if (c=='^')//打表
			{
				a[i][j][0]=1;
			}
			else if (c=='>')//打表
			{
				a[i][j][1]=1;
			}
			else if (c=='v')//打表
			{
				a[i][j][2]=1;
			}
			else if (c=='<')//打表
			{
				a[i][j][3]=1;
			}
			else if (c=='L')//打表
			{
				a[i][j][0]=1;
				a[i][j][1]=1;
				a[i][j][2]=1;
			}
			else if (c=='R')//打表
			{
				a[i][j][0]=1;
				a[i][j][2]=1;
				a[i][j][3]=1;
			}
			else if (c=='U')//打表
			{
				a[i][j][1]=1;
				a[i][j][2]=1;
				a[i][j][3]=1;
			}
			else if (c=='D')//打表
			{
				a[i][j][0]=1;
				a[i][j][1]=1;
				a[i][j][3]=1;
			}
		}
	}
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//讀入
	bfs();//bfs
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}