徐昊轩
(徐昊轩)
1
【题目描述】
大哈已经是个成年人了，网页游戏在他当年还是风靡一时。他记忆中有这么一款游戏。
角色一开始在迷宫的(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
求助，我思路有，但不知道怎么写
3 个赞
徐昊轩
(徐昊轩)
4
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
const int dx[5] = {0,0,0,1,-1};
const int dy[5] = {0,1,-1,0,0};
const long long inf = 2147483647;
using namespace std;
int n,a[1005][1005],t,d[15][105];
int ans;
int v[1005][1005];
bool flag;
struct point{
int x,y,step;
};
deque<point> q;
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
scanf("%d",&a[i][j]),a[i][j] = 0-a[i][j];
scanf("%d",&t);
for(int i = 1;i<=t;i++){
int x,y;
scanf("%d%d%d",&x,&y,&d[i][0]);
a[x][y] = i;
d[i][d[i][0]+1] = x,d[i][d[i][0]+2] = y;
for(int j = 1;j<=d[i][0];j++)
scanf("%d",&d[i][j]);
}
point start = {1,1,0};
v[1][1] = true;
q.push_back(start);
while(!q.empty()){
int x = q.front().x;
int y = q.front().y;
int step = q.front().step;
// printf("%d %d %d\n",x,y,step);
if(x == n && y == n){
ans = step;
flag = true;
break;
}
for(int i = 0;i<=4;i++){
int tx = x + dx[i];
int ty = y + dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&a[tx][ty] != -1 && v[tx][ty] <= 2520){
point temp = {tx,ty,step+1};
v[tx][ty]++;
q.push_back(temp);
}
}
if(a[x][y] >= 1){
int color = d[a[x][y]][step%d[a[x][y]][0]];
for(int i = 1;i<=t;i++){
int nextcolor = d[i][step%d[i][0]];
if(nextcolor == color&&i!=a[x][y]){
int tx = d[i][d[i][0]+1];
int ty = d[i][d[i][0]+2];
if(v[tx][ty]<=2520){
point temp = {tx,ty,step};
v[tx][ty]++;
q.push_front(temp);
}
}
}
}
q.pop_front();
}
if(flag) printf("%d\n",ans);
else printf("-1\n");
}
4 个赞
徐昊轩
(徐昊轩)
5
感觉写的挺对的但TLE，谁能发一下代码我研究一下谢谢
4 个赞
周子寓
(zzy10124)
9
大佬代码指正：
q.pop()应该放在bfs函数while循环的最后一个操作，要不然刚入队就出了，整个队列就是空的
