本文共 3228 字,大约阅读时间需要 10 分钟。
佐助被大蛇丸诱骗走了,鸣人在多少时间内能追上他呢?
输入的第一行包含三个整数:M,N,T。代表 M 行 N 列的地图和鸣人初始的查克拉数量 T。
0 < M,N < 200, 0≤T<10 后面是 M 行 N 列的地图,其中 @ 代表鸣人,+ 代表佐助。* 代表通路,# 代表大蛇丸的手下。输出包含一个整数 R,代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助,则输出 -1。
4 4 1#@##**#####+****
6
4 4 2#@##**#####+****
4
BFS的变种问题,加上了一个状态,所以以前的vis的普通二维的标记是过不了,因为不能判断当前是否为最佳路径,有可能一路杀过来会更快,所以用一个三维数组来标记当前坐标和当前的查克拉量来记录如果有z的查克拉来到x,y的位置有没有走过;
#include#include #include #include #include using namespace std;const int maxn=205;char a[maxn][maxn];int vis[maxn][maxn][15]={ 0};int n,m,ckl,sj;int sx,sy,fx,fy;int dir[4][2]={ { 0,-1},{ 1,0},{ 0,1},{ -1,0}};struct node{ int x,y; int t; int ckl; node(int x,int y,int s,int c):x(x),y(y),t(s),ckl(c){ }};queue q;bool pd(int x,int y){ if(x>=1&&x<=m&&y>=1&&y<=n) return true; else return false;}void bfs(int x,int y,int ckl){ vis[x][y][ckl]=1; q.push(node(x,y,0,ckl)); while(!q.empty()) { node now=q.front(); q.pop(); for(int i=0;i<4;i++) { int nx=now.x+dir[i][0]; int ny=now.y+dir[i][1]; if(pd(nx,ny)&&vis[nx][ny][now.ckl]==0) { if(nx==fx&&ny==fy)//所经过的时间都是1所以第一次到的一定是最短路径 { sj=now.t+1; return; } if(a[nx][ny]=='#'&&now.ckl>0)//如果有敌人而且有查克拉就走 { vis[nx][ny][now.ckl-1]=1; //在此剩余查克拉-1时标记经过了,下次就跳过,因为下次经过此点一定比这次经过的时间要长 q.push(node(nx,ny,now.t+1,now.ckl-1)); } if(a[nx][ny]=='*') { vis[nx][ny][now.ckl]=1; q.push(node(nx,ny,now.t+1,now.ckl)); } } } }}int main(){ memset(vis,0,sizeof(vis)); sj=99999; cin>>m>>n>>ckl;//m行n列 for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { cin>>a[i][j]; if(a[i][j]=='@') { sx=i; sy=j; } if(a[i][j]=='+') { fx=i; fy=j; } } } bfs(sx,sy,ckl); if(sj==99999) { cout<<-1; } else { cout<
最后再附上一个参考别人用二维数组剪枝来写的代码
此题需要特殊判重(判重的意义在于不再走重复的路,防止进入死循环),简单判重只用于到达某位置只是先后次序不同,其他状态相同。而此题由于先后到达某点的路径不同,查克拉的数量可能也会有所不同(甚至会影响是否能到达终点),因此不能简单的判重。 如果后面到达时的查克拉数量大于之前到达的量则可以加入队列(以免走了最前面的路消耗完查克拉最后到达不了终点)#include#include #include #include #include using namespace std;const int maxn=205;char a[maxn][maxn];int vis[maxn][maxn];int n,m,ckl,sj;int sx,sy,fx,fy;int dir[4][2]={ { 0,-1},{ 1,0},{ 0,1},{ -1,0}};struct node{ int x,y; int t; int ckl; node(int x,int y,int s,int c):x(x),y(y),t(s),ckl(c){ }};queue q;void bfs(int x,int y,int ckl){ vis[x][y]=ckl; q.push(node(x,y,0,ckl)); while(!q.empty()) { node now=q.front(); q.pop(); if(a[now.x][now.y]=='+') { sj=now.t; return; } for(int i=0;i<4;i++) { int nx=now.x+dir[i][0]; int ny=now.y+dir[i][1]; if(nx<1||nx>m||ny<1||ny>n) continue; if(a[nx][ny]=='#'&&vis[nx][ny]<=now.ckl)//现有查克拉数要大于之前位置的最大药量才能加入队列 { vis[nx][ny]=now.ckl-1; q.push(node(nx,ny,now.t+1,now.ckl-1)); } else if(a[nx][ny]!='#'&&vis[nx][ny] >m>>n>>ckl; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { cin>>a[i][j]; vis[i][j]=-1; if(a[i][j]=='@') { sx=i; sy=j; } if(a[i][j]=='+') { fx=i; fy=j; } } } bfs(sx,sy,ckl); if(sj==99999) { cout<<-1; } else { cout<
转载地址:http://woagz.baihongyu.com/