简答题
偏难
#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 <bits/stdc++.h>
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<AAA> dl;
AAA tmp, tmp1;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++)
if (s1[i][j] == '@') {
tmp.i = i;
tmp.j = j;
tmp.bs = 0;
tmp.st = t;
break;
}
if (j < n)
break;
}
dl.push(tmp);
for (i = 0; i < 10; i++)
for (j = 0; j < m; j++)
for (k = 0; k < 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 < 4; i++) {
ti = tmp.i + fx[i][0];
tj = tmp.j + fx[i][1];
if ((ti < 0) || (ti >= m) || (tj < 0) || (tj >= n))
continue;
if (s2[t - tmp.st][ti][tj] == 1)
continue;
if ((s1[ti][tj] == '#') && (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", &m, &n, &t);
for (i = 0; i < m; i++)
gets(s1[i]);
printf("%d", bfs());
return 0;
}</pre><p><br/></p><pre class="brush:cpp;toolbar:false">//参考代码2
#include<stdio.h>
#include<algorithm>
#include<string.h>
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<1 || x>n || y<1 || y>m || vis[x][y]) return ;
if(t<0) return ;
if(stp>=minstep) return ;
if(stp>=step[x][y][t]) return ;
step[x][y][t]=stp;
if(mp[x][y]=='#') t--;
else if(mp[x][y]=='+') {
if(stp<minstep) minstep=stp;
return ;
}
vis[x][y]=1;
for(int i=0;i<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",&n,&m,&st);
getchar();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%c",&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<cstdio>
#include<queue>
using namespace std;
struct POINT
{
int x,y,tot,T;
} point;
queue<POINT> 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",&r,&c,&T);
char maze[205][205]={};
for(int i=0;i<r;i++)
{
scanf("%s",maze[i]);
for(int j=0;j<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<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<0 || point.x>=r || point.y<0 || point.y>=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 <bits/stdc++.h>
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 >> m >> n >> k;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
if (a[i][j] == '@') {
mi = i;
mj = j;
}
}
queue<nod> 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 < 4; i++) {
if (t.x + dx[i] < 1 || t.x + dx[i] > m || t.y + dy[i] < 1 ||
t.y + dy[i] > n)
continue;
else if (a[t.x + dx[i]][t.y + dy[i]] == '+') {
cout << t.step + 1;
return 0;
} // 注意:比较查克拉值 好判断该点是否需要更新
else if (a[t.x + dx[i]][t.y + dy[i]] == '*' &&
t.ckl > 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]] == '#' && t.ckl > 0 &&
t.ckl > 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 << "-1";
return 0;
}</pre>
这道题暂未补解析。