hdu-1242 dfs+各种剪枝

思路：

可以和1010一个思路。这个抽象的说就是让你求给定图中两点的最短距离，其实dfs的题目能变化的地方就在“终点的回溯处”，在我们到达终点后，再判断一些附加的值（本题里是最短距离是否更新），从而得到答案。

这题有个坑点，就是图里'x'，即守卫在的点。通常在dfs之前我们都习惯将map[cur_x][cur_y]设置成无法返回的墙，然后在调用完dfs之后再设回通路，而对于x点来说，我们应该将其设置成'x'而不是通路！不然如果the most optimal way如果是后找到的话，那么我们就会受到影响，题目的数据给的不错。。能发现这点

代码：

#include <iostream>

#include <cstring>

#include <cstdio>

#define M 202

#define INF 65535

using namespace std;

int n,m;

char map[M][M];

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

int ans;

void dfs(int cx,int cy,int len) {

    int flag = ;

    //硬条件剪枝

    if(cx<||cy<||cx>n||cy>m) return;

    if(map[cx][cy] == '#') return;

    //软条件剪枝

    if(len >= ans) return;

    if(map[cx][cy] == 'x') {

        len++;

        flag = ;

    }

    if(map[cx][cy] == 'r') {

        ans = len<ans?len:ans;

        return;

    }

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

        int nx = cx+dir[i][];

        int ny = cy+dir[i][];

        map[cx][cy] = '#';

        dfs(nx,ny,len+);

        if(flag) map[cx][cy] = 'x';

        else map[cx][cy] = '.';

    }

}

int main()

{

    int sx,sy;

    while(cin>>n>>m)

    {

        ans = INF;

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

        {

            scanf("%s",map[i]+);

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

                if(map[i][j] == 'a') {

                    sx = i;

                    sy = j;

                }

        }

        dfs(sx,sy,);

        if(ans == INF) {

            cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;

            continue;

        }

        cout<<ans<<endl;

    }

    return ;

}

巴特西

hdu-1242 dfs+各种剪枝

最新文章

热门文章