网站创意模板,技术支持 东莞网站建设家装,视频网站亏损也做,有源码就可以自己做H5网站吗目录
原题描述#xff1a;
【题目描述】
【输入格式】
【输出格式】
【样例输入】
【样例输出】
【数据范围】
题目大意#xff1a;
主要思路#xff1a;
代码code#xff08;附有注释#xff09; 时间限制: 1000ms
空间限制: 524288kB
原题描述#xff1a; …目录
原题描述
【题目描述】
【输入格式】
【输出格式】
【样例输入】
【样例输出】
【数据范围】
题目大意
主要思路
代码code附有注释 时间限制: 1000ms
空间限制: 524288kB
原题描述
【题目描述】
大哈已经是个成年人了网页游戏在他当年还是风靡一时。他记忆中有这么一款游戏。
角色一开始在迷宫的(1,1)处最终要到达(n,n)的位置迷宫中有一些障碍物障碍不能走。同时迷宫中有些点是彩色点彩色点的颜色按照这个点的颜色序列每秒变换一次变完了又会循环比如这个颜色点会这么变“1 2 4”,所以它第一秒是1第二秒是2第三秒是4第四秒又是1依次往复。当你到达彩色点的时候你可以选择把他当普通点直接走上去也可以选择在彩色点传送传送到任意一个此时和它颜色相同的彩色点上传送不需要时间。大哈可以往上下左右走走一格花费1秒他也可以选择不动等一秒因为说不定等一秒下一步就可以直接传送了。大哈现在已经学过一些算法了他想知道到达(n,n)的最短时间是多少
【输入格式】
第一行一个整数n
接下来n行每行n个整数用空格隔开。每个整数是0或者10表示空地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
【数据范围】
n1000, t10, 颜色种类不超过10mi不超过10
题目大意
给你一个矩阵如果是0可以走如果是1不能走没走一步耗时1有些点是彩色点可以传送到与当前彩色点相同的点传送不耗时问你从11走到n,n)最少需要多久。
主要思路
既然是最少又是每次走都是1很明显bfs思路上没啥难度。
代码code附有注释
#includebits/stdc.h
using namespace std;
int dx[] {0,-1,0,1};
int dy[] {1,0,-1,0};
mappairint,int,int mp;
mapint,pairint,int mp1;
int a[1010][1010];
int f[1010][1010];
int dis[1010][1010];
int t,n;
void bfs()
{memset(dis,0x3f,sizeof(dis));queuepairint,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 ump[{x,y}];int vdis[x][y];for(int i0;i2520;i)//枚举秒{for(int j1;jt;j)//枚举颜色点{if(j u){continue;}int z (vi)%f[u][0],m(vi)%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]vi)//如果路径可以更小{dis[tx][ty] vi;//变成更小路径q.push({tx,ty});//加入队列}}}}}for(int i0;i4;i)//选择走{int txxdx[i],tyydy[i];if(tx1||txn||ty1||tyn||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{coutdis[n][n];}
}
int main()
{
// int n;cinn;for(int i1;in;i){for(int j1;jn;j){cina[i][j];}}cint;for(int i1;it;i){int x,y;cinxy;cinf[i][0];mp[{x,y}] i;//{x,y}是第i个颜色点mp1[i] {x,y};//第i个颜色点是{x,y};for(int j1;jf[i][0];j){cinf[i][j];}}bfs();return 0;
}
