大哈的变换迷宫的题解

时间限制: 1000ms

空间限制: 524288kB

原题描述：

【题目描述】

大哈已经是个成年人了，网页游戏在他当年还是风靡一时。他记忆中有这么一款游戏。

角色一开始在迷宫的(1,1)处，最终要到达(n,n)的位置，迷宫中有一些障碍物，障碍不能走。同时迷宫中有些点是彩色点，彩色点的颜色按照这个点的颜色序列每秒变换一次，变完了又会循环，比如这个颜色点会这么变，“1 2 4”,所以它第一秒是1，第二秒是2，第三秒是4，第四秒又是1，依次往复。当你到达彩色点的时候，你可以选择把他当普通点直接走上去，也可以选择在彩色点传送，传送到任意一个此时和它颜色相同的彩色点上，传送不需要时间。大哈可以往上下左右走，走一格花费1秒，他也可以选择不动，等一秒，因为说不定等一秒，下一步就可以直接传送了。大哈现在已经学过一些算法了，他想知道到达(n,n)的最短时间是多少？

【输入格式】

第一行，一个整数n

接下来n行，每行n个整数，用空格隔开。每个整数是0或者1，0表示空地，1表示障碍物。保证起点和终点都是0

接下来1行，一个整数t，表示彩色格子的数量

接下来t行，每行第一个和第二个整数xi和yi表示这个彩色格子的坐标；第三个整数mi，表示第i个彩色格子的颜色序列长度，后面跟着mi个整数，表示当前这个彩色点的颜色变换顺序

【输出格式】

一个整数，表示到达终点的最短时间，如果不能到达终点，输出-1.

【样例输入】

5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 1 1
0 0 1 0 0
3
2 2 3 1 2 3
3 4 5 1 2 1 2 4
5 4 4 5 5 5 4

【样例输出】

21

【数据范围】

n<=1000, t<=10, 颜色种类不超过10，mi不超过10

题目大意：

给你一个矩阵，如果是0，可以走，如果是1，不能走，没走一步耗时1，有些点是彩色点，可以传送到与当前彩色点相同的点，传送不耗时，问你从（1，1）走到（n,n)最少需要多久。

主要思路：

既然是最少，又是每次走都是1，很明显bfs，思路上没啥难度。

代码code（附有注释）

#include<bits/stdc++.h>
using namespace std;
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};
map<pair<int,int>,int> mp;
map<int,pair<int,int>> mp1;
int a[1010][1010];
int f[1010][1010];
int dis[1010][1010];
int t,n;
void bfs()
{
	memset(dis,0x3f,sizeof(dis));
	queue<pair<int,int>> q;
	q.push({1,1});
	dis[1][1] = 0;
	while(!q.empty())
	{
		auto [x,y] = q.front();
		q.pop();
		if(mp[{x,y}])//如果这是一个颜色点，可以选择传送
		{
			int u=mp[{x,y}];
			int v=dis[x][y];
			for(int i=0;i<=2520;i++)//枚举秒
			{
				for(int j=1;j<=t;j++)//枚举颜色点
				{
					if(j == u)
					{
						continue;
					}
					int z = (v+i)%f[u][0],m=(v+i)%f[j][0];//计算一下第i秒是啥颜色点
					if(z == 0)
					{
						z = f[u][0];
					}
					if(m == 0)
					{
						m = f[j][0];
					}
					//判断一下
					if(f[u][z] == f[j][m])//匹配
					{
						auto [tx,ty] = mp1[j];
						if(dis[tx][ty]>v+i)//如果路径可以更小
						{
							dis[tx][ty] = v+i;//变成更小路径
							q.push({tx,ty});//加入队列
						}
					}
				}
			}
		}
		for(int i=0;i<4;i++)//选择走
		{
			int tx=x+dx[i],ty=y+dy[i];
			if(tx<1||tx>n||ty<1||ty>n||a[tx][ty] == 1)
			{
				continue;
			}
			if(dis[tx][ty]>dis[x][y]+1)
			{
				dis[tx][ty] = dis[x][y]+1;
				q.push({tx,ty});
			}
		}
	}
	if(dis[n][n]>1e9)//如果走不到
	{
		cout<<"-1";
	}
	else{
		cout<<dis[n][n];
	}
}
int main()
{
//	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		int x,y;
		cin>>x>>y;
		cin>>f[i][0];
		mp[{x,y}] = i;//{x,y}是第i个颜色点
		mp1[i] = {x,y};//第i个颜色点是{x,y};
		for(int j=1;j<=f[i][0];j++)
		{
			cin>>f[i][j];
		}
	}
	bfs();
	return 0;
}