首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7472

鸣人和佐助(2023.12) 描述 佐助被大蛇丸诱骗走了,鸣人在多少时间内能追上他呢? 已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位…

鸣人和佐助(2023.12)

描述

佐助被大蛇丸诱骗走了,鸣人在多少时间内能追上他呢?

已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位置都可以走到,只不过有些位置上有大蛇丸的手下,需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉,每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动,每移动一个距离需要花费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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int n, m, t, s2[10][256][256], fx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; char s1[256][256]; struct AAA {   int i;   int j;   int bs;   int st; }; int bfs() {   int i, j, k, ti, tj, ret = -1;   queue&lt;AAA&gt; dl;   AAA tmp, tmp1;   for (i = 0; i &lt; m; i++) {     for (j = 0; j &lt; n; j++)       if (s1[i][j] == '@') {         tmp.i = i;         tmp.j = j;         tmp.bs = 0;         tmp.st = t;         break;       }     if (j &lt; n)       break;   }   dl.push(tmp);   for (i = 0; i &lt; 10; i++)     for (j = 0; j &lt; m; j++)       for (k = 0; k &lt; n; k++)         s2[i][j][k] = 0;   s2[0][tmp.i][tmp.j] = 1;   while (!dl.empty()) {     tmp = dl.front();     dl.pop();     if (s1[tmp.i][tmp.j] == '+') {       ret = tmp.bs;       break;     }     for (i = 0; i &lt; 4; i++) {       ti = tmp.i + fx[i][0];       tj = tmp.j + fx[i][1];       if ((ti &lt; 0) || (ti &gt;= m) || (tj &lt; 0) || (tj &gt;= n))         continue;       if (s2[t - tmp.st][ti][tj] == 1)         continue;       if ((s1[ti][tj] == '#') &amp;&amp; (tmp.st == 0))         continue;       s2[t - tmp.st][ti][tj] = 1;       tmp1.i = ti;       tmp1.j = tj;       tmp1.bs = tmp.bs + 1;       tmp1.st = tmp.st;       if (s1[ti][tj] == '#')         tmp1.st--;       dl.push(tmp1);     }   }   return ret; } int main() {   int i, j, k;   char tmp[16];   gets(tmp);   sscanf(tmp, "%d%d%d", &amp;m, &amp;n, &amp;t);   for (i = 0; i &lt; m; i++)     gets(s1[i]);   printf("%d", bfs());   return 0; }</pre><p><br/></p><pre class="brush:cpp;toolbar:false">//参考代码2 #include&lt;stdio.h&gt; #include&lt;algorithm&gt; #include&lt;string.h&gt; using namespace std; const int inf=0x3f3f3f3f; int n,m,sx,sy,st,minstep=inf; int step[201][201][11],dx[]={0,1,-1,0},dy[]={1,0,0,-1}; char mp[201][201]; bool vis[201][201]; void dfs(int x,int y,int t,int stp) {     if(x&lt;1 || x&gt;n || y&lt;1 || y&gt;m || vis[x][y]) return ;     if(t&lt;0) return ;     if(stp&gt;=minstep) return ;     if(stp&gt;=step[x][y][t]) return ;     step[x][y][t]=stp;          if(mp[x][y]=='#') t--;     else if(mp[x][y]=='+') {         if(stp&lt;minstep) minstep=stp;         return ;     }          vis[x][y]=1;     for(int i=0;i&lt;4;++i){         int nx=x+dx[i];         int ny=y+dy[i];         dfs(nx,ny,t,stp+1);     }     vis[x][y]=0; } int main() {     scanf("%d%d%d",&amp;n,&amp;m,&amp;st);     getchar();     for(int i=1;i&lt;=n;++i){         for(int j=1;j&lt;=m;++j){             scanf("%c",&amp;mp[i][j]);             if(mp[i][j]=='@') {                 sx=i;                 sy=j;             }         }         getchar();     }     memset(step,0x3f,sizeof(step));     dfs(sx,sy,st,0);     if(minstep==inf) printf("-1");     else printf("%d",minstep);     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码3 #include&lt;cstdio&gt; #include&lt;queue&gt; using namespace std; struct POINT {     int x,y,tot,T; } point; queue&lt;POINT&gt; que; int main() {     bool walked[205][205][15]={};     int r,c,T,F[4][2]={{-1,0},{1,0},{0,-1},{0,1}};     scanf("%d%d%d",&amp;r,&amp;c,&amp;T);     char maze[205][205]={};     for(int i=0;i&lt;r;i++)     {         scanf("%s",maze[i]);         for(int j=0;j&lt;c;j++)             if(maze[i][j]=='@')             {                 point.x=i;point.y=j;                 point.tot=0;point.T=T;             }     }     que.push(point);     while(!que.empty())     {         for(int i=0;i&lt;4;i++)         {             point.x=que.front().x+F[i][0];             point.y=que.front().y+F[i][1];             point.tot=que.front().tot+1;             point.T=que.front().T;             if(point.x&lt;0 || point.x&gt;=r || point.y&lt;0 || point.y&gt;=c || walked[point.x][point.y][point.T]) continue;             if(maze[point.x][point.y]=='#')                 if(point.T) point.T--;                 else continue;             if(maze[point.x][point.y]=='+') {printf("%d\n",point.tot);return 0;}             walked[point.x][point.y][point.T]=true;             que.push(point);         }         que.pop();     }     printf("-1\n");     return 0; }</pre><pre class="brush:cpp;toolbar:false">// 参考代码4 #include &lt;bits/stdc++.h&gt; using namespace std; char a[202][202]; int v_ckl[202][202]; // 走到该坐标点时的最小消耗的查克拉 struct nod {   int x, y, ckl, step; }; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int main() {   int n, m, k, mi, mj;   cin &gt;&gt; m &gt;&gt; n &gt;&gt; k;   for (int i = 1; i &lt;= m; i++)     for (int j = 1; j &lt;= n; j++) {       cin &gt;&gt; a[i][j];       if (a[i][j] == '@') {         mi = i;         mj = j;       }     }   queue&lt;nod&gt; q;   q.push({mi, mj, k, 0});   v_ckl[mi][mj] = k;   memset(v_ckl, -1,          sizeof(v_ckl)); // 注意:初始值 查克拉为零时条件允许也可以走的   while (!q.empty()) {     nod t = q.front();     q.pop();     for (int i = 0; i &lt; 4; i++) {       if (t.x + dx[i] &lt; 1 || t.x + dx[i] &gt; m || t.y + dy[i] &lt; 1 ||           t.y + dy[i] &gt; n)         continue;       else if (a[t.x + dx[i]][t.y + dy[i]] == '+') {         cout &lt;&lt; t.step + 1;         return 0;       } // 注意:比较查克拉值 好判断该点是否需要更新       else if (a[t.x + dx[i]][t.y + dy[i]] == '*' &amp;&amp;                t.ckl &gt; v_ckl[t.x + dx[i]][t.y + dy[i]]) {         q.push({t.x + dx[i], t.y + dy[i], t.ckl, t.step + 1});         v_ckl[t.x + dx[i]][t.y + dy[i]] = t.ckl;       } else if (a[t.x + dx[i]][t.y + dy[i]] == '#' &amp;&amp; t.ckl &gt; 0 &amp;&amp;                  t.ckl &gt; v_ckl[t.x + dx[i]][t.y + dy[i]]) {         q.push({t.x + dx[i], t.y + dy[i], t.ckl - 1, t.step + 1});         v_ckl[t.x + dx[i]][t.y + dy[i]] = t.ckl - 1;       }     }   }   cout &lt;&lt; "-1";   return 0; }</pre>
这道题暂未补解析。