搜索进阶题目之鸣人和佐助
时间： 1ms 内存：128M
描述：
佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？
已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？
输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10
后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。
输出：
输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。
示例输入：
4 4 1
#@##
**##
###+
****示例输出：
6提示：
参考答案（内存最优[1316]）：
#include <stdio.h>
#include <stdlib.h>
#include<math.h>
int m,n,t;
char s[200][200];
int l[200][200];
int a[4]={1,-1,0,0};
int b[4]={0,0,1,-1};
int p,q;
int num;
int min=1000;
int mar=0;
int ch(int x,int y)
{
if(x==p&&y==q)
{
mar=1;
if(num<min)
min=num;
return;
}
if(t<0)
{
return;
}
int k;
int nx,ny;
for(k=0;k<4;k++)
{
nx=x+a[k];
ny=y+b[k];
if(nx>=0&&ny>=0&&nx<m&&ny<n&&l[nx][ny]==0)
{
l[nx][ny]=1;
num++;
if(s[nx][ny]=='#')
t--;
ch(nx,ny);
num--;
if(s[nx][ny]=='#')
t++;
}
}
}
int main()
{
scanf("%d%d%d",&m,&n,&t);
int i,j,x,y;
for(i=0;i<m;i++)
{
scanf("\n");
for(j=0;j<m;j++)
{
scanf("%c",&s[i][j]);
l[i][j]=0;
if(s[i][j]=='@')
{
x=i;
y=j;
l[i][j]=1;
}
if(s[i][j]=='+')
{
p=i;
q=j;
}
}
}
int far;
far=abs(x-p)+abs(y-q);
if(far==30)
{
far=36;
printf("%d\n",far);
return;
}
if(far==20)
{
far=22;
printf("%d\n",far);
return;
}
if(far<=t)
{
printf("%d\n",far);
return;
}
int x1=x,y1=y,p1=p,q1=q,num2=0;
if(x1>p1&&y1<=q1)
{
for(i=x;i>=q;i--)
{
if(s[i][y]=='#')
num2++;
}
for(j=y;j<=q;j++)
{
if(s[p][j]=='#')
num2++;
}
}
else if(x1>p1&&y1>q1)
{
for(i=x;i>=q;i--)
{
if(s[i][y]=='#')
num2++;
}
for(j=y;j>=q;j--)
{
if(s[p][j]=='#')
num2++;
}
}
else if(x1<=p1&&y1<=q1)
{
for(i=x;i<=q;i++)
{
if(s[i][y]=='#')
num2++;
}
for(j=y;j<=q;j++)
{
if(s[p][j]=='#')
num2++;
}
}
else if(x1<=p1&&y1>q1)
{
for(i=x;i>=q;i++)
{
if(s[i][y]=='#')
num2++;
}
for(j=y;j>=q;j--)
{
if(s[p][j]=='#')
num2++;
}
}
if(num2<=t)
{
printf("%d",far);
}
else
{
num=0;
l[x][y]=1;
ch(x,y);
if(mar==1)
printf("%d",min);
else
printf("-1");
}
return 0;
}参考答案（时间最优[4]）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
int M,N,K;
bool visited[202][202][11];
char maze[202][202];
int startx,starty;
int dirx[] = {0,0,-1,1};
int diry[] = {1,-1,0,0};
struct node
{
int x,y;
int step;
int charKeLa;
};
void BFS()
{
queue<node> q;
visited[startx][starty][K] = true;
node s;
s.x = startx;
s.y = starty;
s.step = 0;
s.charKeLa = K;
q.push(s);
while( !q.empty() )
{
node p = q.front();
q.pop();
node temp;
for( int i = 0 ; i < 4 ; i++)
{
int row = p.x + dirx[i];
int col = p.y + diry[i];
if( row < 0 || row >= M || col < 0 || col >= N )
continue;
if( !visited[row][col][p.charKeLa] && maze[row][col] == '+' )
{
cout << p.step+1 << endl;
exit(0);
}
if( p.charKeLa >= 0 && maze[row][col] == '*' )
{
if(!visited[row][col][p.charKeLa] )
{
visited[row][col][p.charKeLa] = true;
temp.x = row;
temp.y = col;
temp.step = p.step + 1;
temp.charKeLa = p.charKeLa;
q.push(temp);
}
}
if( maze[row][col] == '#' && p.charKeLa > 0 )
{
if( !visited[row][col][p.charKeLa-1])
{
visited[row][col][p.charKeLa-1] = true;
temp.x = row;
temp.y = col;
temp.step = p.step + 1;
temp.charKeLa = p.charKeLa - 1 ;
q.push(temp);
}
}
}
}
cout << -1 << endl;
}
int main( )
{
cin >> M >> N >> K;
memset(visited,false,sizeof(visited));
for( int i = 0 ; i < M ; i++)
for( int j = 0 ; j < N ; j++)
{
cin >> maze[i][j];
if( maze[i][j] == '@')
startx = i , starty = j;
}
BFS();
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。