P2802 回家（DFS+剪枝）

拼搏现实的明天。 2021-12-15 08:47 258阅读 0赞

这里详细讲一下剪枝的点：

因为，可以重复在同一个点上走动。所以，这个步数是无穷的。

剪枝一：步数< n\*m;    (因为起点不算所以不取等号)

剪枝二：步数当大于已有的答案时，直接退出DFS，因为你已经知道这个线路不是答案了，那就没有必要走出去的必要了。（当时，没想到，还傻傻的想了半天）

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    const int inf = 0x3f3f3f;
    int xx[] = { 0, 1, -1, 0, 0 };
    int yy[] = { 0, 0, 0, 1, -1 };
    int f[11][11];
    int n, m, ans=inf, x1, yk, x2, y2;
    
    void dfs(int x, int y, int k, int sum){
        if (sum >= n*m)return;
        if (k == 0||sum>ans)return;
        if (x == x2&&y == y2){ ans = min(ans, sum); return; }
        for (int i = 1; i <= 4; ++i){
            int xk = x + xx[i];
            int yk = y + yy[i];
            if (xk >= 1 && xk <= n&&yk >= 1 && yk <= m && (f[xk][yk] == 4 || f[xk][yk] == 1||f[xk][yk]==3)){
                if (k - 1 == 0)return;
                if (f[xk][yk] == 4){ dfs(xk, yk, 6, sum + 1); }
                else dfs(xk, yk, k - 1, sum + 1);
            }
        }
    
    }
    
    int main(){
        cin >> n >> m;
        for (int i = 1; i <= n;++i)
        for (int j = 1; j <= m; ++j)
        {
            cin >> f[i][j];
            if (f[i][j] == 2){ x1 = i; yk = j; }
            else if (f[i][j] == 3){ x2 = i; y2 = j; }
        }
        dfs(x1, yk, 6, 0);
        if (ans == inf)cout << -1 << endl;
        else cout << ans << endl;
    }

转载于:https://www.cnblogs.com/ALINGMAOMAO/p/10660058.html

发表评论取消回复

表情：

评论列表（有 0 条评论，258人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 1011 DFS+剪枝

目是英文的翻译过来大概是这个意思：现在有一些长度相同的棍子，将这些棍子随意切割成n个长度不一的棍子。题目会给出n和这n个棍子的长度，求原来棍子长度的最小值。也可以反...

系统管理员/ 2024年04月19日 11:17/ 0 赞/ 32 阅读

相关奇偶剪枝+ DFS

<table> <tbody> <tr> <td> <h2>Tempter of the Bone</h2> <strong>Time Limit: 2000

约定不等于承诺〃/ 2024年02月18日 23:05/ 0 赞/ 15 阅读

相关 dfs奇偶剪枝---HDU - 1010

题意：问小狗是否能在第T秒（走T步）从S点到达D点思路：很明显的一道dfs题目，但是我们这里需要采用剪枝减少不必要的路，另外这里的地图是字符，我们输入需要注意吸收换行符

客官°小女子只卖身不卖艺/ 2023年08月17日 16:25/ 0 赞/ 83 阅读

相关 Poj 1190 生日蛋糕 (DFS 剪枝)

隐约记得前几年网络赛有过类似的题，当时毫无想法…… 参考了：http://blog.csdn.net/lencle/article/details/7016191 可能还能

ゞ浴缸里的玫瑰/ 2022年09月20日 13:00/ 0 赞/ 130 阅读

相关 dfs+剪枝 poj1011

大致题意：给定一堆不定长度的小棒子，问他们能否构成一个正方形。思路：对所有的棒子求和sum之后除以4，得到边长side，问题就转换为求这些棒子能否拼接成4个长度为side的

小咪咪/ 2022年08月03日 16:54/ 0 赞/ 144 阅读

相关 Tempter of the Bone(DFS+剪枝)

Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/327

约定不等于承诺〃/ 2022年08月02日 14:58/ 0 赞/ 139 阅读

相关 HDU 1455 Sticks（dfs+强剪枝）

题目： Description George took sticks of the same length and cut them randomly until all

红太狼/ 2022年06月13日 07:50/ 0 赞/ 140 阅读

相关九宫格问题（dfs+剪枝）

你一定听说过“数独”游戏。如【图1.png】，玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个同色九宫内的数字均含1

青旅半醒/ 2022年05月29日 13:27/ 0 赞/ 234 阅读

相关蓝桥杯 dfs+剪枝

include <cstdio> include <cstring> using namespace std; int num[15]={0};

梦里梦外;/ 2022年05月29日 12:50/ 0 赞/ 144 阅读

相关 P2802 回家（DFS+剪枝）

这里详细讲一下剪枝的点：　　因为，可以重复在同一个点上走动。所以，这个步数是无穷的。　　剪枝一：步数< n\m; (因为起点不算所以不取等号) 　　剪枝二：步数

拼搏现实的明天。/ 2021年12月15日 08:47/ 0 赞/ 259 阅读