题目链接http://noi.openjudge.cn/ch0205/6044/
- 描述
-
佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？
已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？
- 输入
- 输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10
后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。 - 输出
- 输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。
- 样例输入
-
样例输入1 4 4 1 #@## **## ###+ **** 样例输入2 4 4 2 #@## **## ###+ ****
- 样例输出
-
样例输出1 6 样例输出2 4
查看
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<string> #include<vector> #define DEBUG(x) cout<<#x<<" = "<<x<<endl using namespace std; const int MAXN=210; const int INF=0x3f3f3f3f; int M,N,T; char Map[MAXN][MAXN]; int visited[MAXN][MAXN]; int steps[MAXN][MAXN][15]; int minStep=INF; int dirx[]={1,-1,0,0}; int diry[]={0,0,1,-1}; void dfs(int x,int y,int t,int step) {///位于x,y,已经走了step步 ///t表示剩余的查克拉，需要注意的是t必须在本次调用内更新 ///不能提前更新 // DEBUG(x); // DEBUG(y); // DEBUG(Map[x][y]); // DEBUG(t); // DEBUG(step); // printf(" "); if(x<0||y<0||x>=M||y>=N||visited[x][y])return; if(t<0)return; if(step>=minStep)return; if(step>=steps[x][y][t])return; steps[x][y][t]=step; if(Map[x][y]=='#')t--;/// if(Map[x][y]=='+'){ if(step<minStep)minStep=step; return; } visited[x][y]=1; for(int i=0;i<4 ;i++ ){ int xx=x+dirx[i]; int yy=y+diry[i]; //if(Map[xx][yy]=='*')提前更新会导致状态的不一致性 dfs(xx,yy,t,step+1); //else //dfs(xx,yy,t-1,step+1); } visited[x][y]=0; } int main() { // freopen("in.txt","r",stdin); scanf("%d%d%d",&M,&N,&T); getchar(); int x,y; for(int i=0;i<M ;i++ ){ for(int j=0;j<N ;j++ ){ scanf("%c",&Map[i][j]); if(Map[i][j]=='@'){ x=i,y=j; } } getchar(); } memset(steps,0x3f,sizeof(steps)); dfs(x,y,T,0); if(minStep!=INF)printf("%d ",minStep); else puts("-1"); }
广搜做法
关键是状态的设计，状态可以设计成一个三元组，位置坐标x,y和到达该位置所剩的查克拉数目
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<string> #include<vector> #include<queue> #define DEBUG(x) cout<<#x<<" = "<<x<<endl using namespace std; const int MAXN=210; const int INF=0x3f3f3f3f; int M,N,T; char Map[MAXN][MAXN]; int visited[MAXN][MAXN][15]; int dirx[]={1,-1,0,0}; int diry[]={0,0,1,-1}; struct Node{ int x,y,k; int step; Node(int xx,int yy,int kk,int s):x(xx),y(yy),k(kk),step(s){} }; queue<Node>q; bool legal(int x,int y) { return x<M&&x>=0&&y<N&&y>=0; } int main() { // freopen("in.txt","r",stdin); scanf("%d%d%d",&M,&N,&T); getchar(); int x,y; for(int i=0;i<M ;i++ ){ for(int j=0;j<N ;j++ ){ scanf("%c",&Map[i][j]); if(Map[i][j]=='@'){ x=i,y=j; } } getchar(); } memset(visited,0,sizeof(visited)); q.push(Node(x,y,T,0)); visited[x][y][T]=true; while(!q.empty()){ Node t=q.front(); q.pop(); if(Map[t.x][t.y]=='+'){ printf("%d ",t.step); return 0; } for(int i=0;i<4 ;i++ ){ int xx=t.x+dirx[i]; int yy=t.y+diry[i]; if(legal(xx,yy)){ if(Map[xx][yy]=='#'){ if(t.k>0){ if(!visited[xx][yy][t.k-1]){ q.push(Node(xx,yy,t.k-1,t.step+1)); visited[xx][yy][t.k-1]=true; } } } else { if(!visited[xx][yy][t.k]){ q.push(Node(xx,yy,t.k,t.step+1)); visited[xx][yy][t.k]=true; } } } } } puts("-1"); }