搜索进阶题目之鸣人和佐助

时间: 1ms        内存:128M

描述:


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

已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位置都可以走到,只不过有些位置上有大蛇丸的手下,需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉,每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动,每移动一个距离需要花费1个单位时间,打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了,则只可以走到没有大蛇丸手下的位置,不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动,大蛇丸的手下也不移动。请问,鸣人要追上佐助最少需要花费多少时间?




输入的第一行包含三个整数:MNT。代表MN列的地图和鸣人初始的查克拉数量T0 < M,N < 2000 ≤ T < 10
后面是MN列的地图,其中@代表鸣人,+代表佐助。*代表通路,#代表大蛇丸的手下。

输出:


输出包含一个整数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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。