HDU_1072_Nightmare

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1072

题目描述：矩阵表示迷宫，0表示墙，1表示路，2表示起点，3表示终点，4表示重置炸弹时间（6秒），你需要从起点出发（炸弹初始为6秒），在炸弹爆炸前到达终点，问最少需要多少时间。

分析：dfs，可以走走过的路，所以不能使用vis数组来标记，而是用dis和tim两个数组来帮助判断所走路线，通过这两个数组的记录来剪枝（此处剪枝：当sum大于dis[x][y]且time<=tim[x][y]说明当前这条路并非最佳路线，此处着重理解）。

总结：dfs摸到的些许门道，还需加强，剪枝还需要多见识一些。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

#define INF 100

int map[][];

int dir[][]= {{-,},{,},{,},{,-}};

int dis[][];

int tim[][];

int n,m,minx;

bool inside(int x,int y)

{

    if(x<n&&x>=&&y<m&&y>=)

        return ;

    return ;

}

void dfs(int x,int y,int time,int sum)

{

    if(map[x][y]==&&time>)

    {

        if(sum<minx)

            minx=sum;

        return;

    }

    if(time<=)

        return;

    if(map[x][y]==)

        return;

    if(!inside(x,y))

        return;

    if(time<=tim[x][y]&&sum>=dis[x][y])  //剪枝

        return;

    if(map[x][y]==)

        time=;

    dis[x][y]=sum;

    tim[x][y]=time;

    for(int i=; i<; i++)

    {

        int mx=x+dir[i][];

        int my=y+dir[i][];        dfs(mx,my,time-1,sum+1);

    }

}

int main()

{

    int t,sx,sy,ex,ey;

    scanf("%d",&t);

    while(t--)

    {

        memset(tim,,sizeof(tim));

        minx=INF;

        scanf("%d%d",&n,&m);

        for(int i=; i<n; i++)

            for(int j=; j<m; j++)

                dis[i][j]=INF;

        for(int i=; i<n; i++)

            for(int j=; j<m; j++)

            {

                scanf("%d",&map[i][j]);

                if(map[i][j]==)

                {

                    sx=i;

                    sy=j;

                }

            }

        dfs(sx,sy,,);

        if(minx!=INF)

            printf("%d\n",minx);

        else

            printf("-1\n");

    }

    return ;

}

巴特西

HDU_1072_Nightmare

最新文章

热门文章