普及练习场

知识点汇总：DFS、BFS、☆杨辉三角P1118 USACO06FEB 数字三角形☆

求解的个数用深搜，求最优解用广搜。

DFS

P1219 八皇后

弱智一样的我，还建立NxN的矩阵来模拟。

结果呢，检查(check)时要遍历整个棋盘，最终导致只能过部分。

根本不用二维矩阵。

dfs(i)，因为传进来的i是行号，可以保证这一行只有一个。

然后这一行放在第j列可以吗？根本不用遍历棋盘。

只需要三个check数组，做标志位。

P1019 单词接龙

这题我晚上做的。代码觉得没问题但是跑起来没输出。就睡了。第二天起来，删了几句代码精简了下结构。也不知道因为改了哪，直接AC了。

总之这题虽是基础的DFS。但我思路还挺清晰的。有空可以回看一下代码！

注意：能不“模拟”的尽量别搞这么复杂，就像八皇后没必要传入一个棋盘一样！

P1101 单词方阵

先说一下我的一些问题：

  • 往一个方向搜就搜到头，没想到搜够7个字符就停止

然后看到题解人家在做8个方向时，用了一个二维数组，分别存i和j的变量：

1
int dir[][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};//八向的常量数组

BFS

P1162 填涂颜色

BFS第一道，龙哥说BFS就是队列。树的层序遍历。

那这题我就会了啊。但是经历了下面的波折：

  • 用了queue做，思路很清晰。看关键代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    while (!q1.empty()){
            node temp=q1.front();
            int i=temp.x,j=temp.y;
        	for(int k=0;k<4;k++){//四个方向找联通块，找到入队
                if(a[i+dir[k][0]][j+dir[k][1]]==0)
                    q1.push(node(i+dir[k][0],j+dir[k][1]))
            }
            a[i][j]=2;
            q1.pop();
            cout<<"computing\n";
    }

    5个用例，最后一个数据过不了，下载了看，30x30矩阵，然后外圈是1中间全0.应该是卡在四个方向寻找那里了。这么多数都入队。（特别我没考虑到上面的写法让很多点多次入队）

  • 以为是queue的问题(其实不是，queue完全可以AC)，看了题解，准备用数组做。

    数组模拟队列，用两个下标控制队头队尾。调试后发现1、5用例AC。234又过不了。Debug后找出了下面的错误：

    • 每次取队头begin后，不把它先存到另一个变量了。直接在begin上操作。导致每入队一个数，队头就后移。

    • 这次知道把begin取出来用另一个变量来控制往里存数了。1-4用例AC。第五个又超时了。Debug一下发现队列的下标都到2000多了。照理说我30x30的矩阵，所有的点入队才900个点而已啊！怎么会有这么多点入队呢。

      这时候才领悟到：很多点多次入队

      应该发现是0联通块，直接改成2，然后再把它入队。不然另外和Ta相邻的点，又看到Ta符合条件又会让它入队。AC

  • 发现不是queue问题后。改又了queue版代码，AC。

  • 最后：操作i\j下标记得用方向数组啊。美观很多。

P1032 字串变换

这个数据太刁钻了：

1
2
3
4
5
6
7
abaaaba abcdaba
a b
b d
d e
e f
f g
g c

哎。我最后特判的。

P1141 01迷宫

  • 我发现传vector变量的地方可以直接传{1,2,3,4,5}进去

样例2过不了竟是因为用了这种结构。改用结构体之后直接ac

这样我就不用使用一个结构体来存(x,y)坐标了啊。直接：

1
2
  queue<vector<int>> queue1;
queue1.push({i,j});

方便。但以后还是老老实实结构体吧

  • # 2 9 10 三个用例超时。#2是一个1000*1000的矩阵。10w条数据。我已经使用了记忆化搜索。实在想不到哪里可以优化了。

  • 好像想出来我的问题了，我虽然使用了记忆化。但是我是把遍历到的联通块每个点的答案都存了起来。就是说我求出来了整个地图的解。看似读取快了。实际计算了很多不必须要的答案。应该只求输入里有的点就好。

P1126 机器人搬重物

拿到题：

1
2
3
//先分析一下。输入坐标其实是球的右下角。
// 所以在判断下、右墙面时，直接判断。判断上、左墙面时，要隔两个身位。
//初步思路就是这样。

Notice:

  • 如果这个方向有障碍就不用看走更多步数的情况了，不是说走3步那个地方没有障碍就能走过去。可能障碍在走两步那出现。

P1443 马的遍历

简单bfs，需要注意的是答案要求5个字符左对齐: %-5d

如果是c++则要：

1
2
cout.setf(std::ios::left);//左对齐，全局有效
cout.width(5);//宽度，每次设置只影响下一次cout

带有技巧的搜索

P1118 USACO06FEB 数字三角形

关于杨辉三角

记住下面两个知识点，

  • 通项公式

    第n行的第m个数 其实是排列组合数$C_{n-1}^{m-1}$

    如第4行4个数是$C_3^0=1,C_3^1=3,C_3^2=3,C_3^3=1$

    第5行5个数是$C_4^0=1,C_4^1=4,C_4^2=\frac{4\times3}{2\times1}=6,C_4^3=4,C_4^4=1$

  • 利用前一个数求后一个，

    $第i个数=第{i-1}个数\times \frac{n-i}{i},i取0到n-1$

    记住这段代码：

    1
    2
    3
    4
      int a[n];//假设求第n行
      a[0]=a[n-1]=1;//两端赋值1
    for (int i=1;i*2<n;i++)
          a[i]=a[n-1-i]
          =a[i-1]*(n-i)/i;//利用对称一次填充两个

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96

      细节：

      - ` a[0]`对应``a[n-1]`,故`a[i]`对应`a[n-1-i]`

      - 如求第4行 $a_0=a_3=1$ **首尾先赋值**

        $a_1=a_3=a_0\times\frac{4-1}{1}=1\times3=3$ **对称填充**
      
        求第5行 $a_0=a_4=1$ **首尾先赋值**
      
        $a_1=a_3=a_0\times\frac{5-1}{1}=1\times4=4$ **对称填充**
      
        $a_2=a_1\times\frac{5-2}{2}=4\times\frac{3}{2}=6$

    ---

    回到此题

    ### dfs法

    有了杨辉三角做系数。配合DFS对1-N的数做个排列组合。所有的情况都选出来这题就解决了。下面说一下这题的剪枝：

    - 开始我是把所有的情况都dfs了。然后**当枚举结束时**，计算sum是不是要求的数。然后如果累加的过程中如果sum超了，就不再往下算了。
    - 但是仔细想想。这不还是枚举出了所有的情况吗。随后一步求sum我优化个屁啊。
    - 正解：在**DFS的过程中**，取一个数就加到sum里，**这样不用等枚举结束，就能把行不通的路减掉**。

    ### next_permutation

    容易看出这题不用dfs的话可以借助`<algorithm.h>`里的`next_permutation()`，

    默认是从小到大排序的。比如原来是1234.那么next_permutation()就是1243。

    问题在于如何剪枝。（不然就是全部枚举的dfs，和上面一样）

    - 当发现已经不行时，对后面的数进行sort。并让大的在前。

      例子：现在数组为 2 3 1 4

      处理完23发现 23开头的都不行。（那就没必要枚举出 2341了。）

      `sort(,,greater<int>())`后数组变成 2341 跳出循环

      再次执行next_permutation()就跳过了（剪枝了）

      

    ## [P1434 SHOI2002 滑雪](https://www.luogu.org/problemnew/show/P1434)

    - 开始想错了思路。搞成了联通块。后来仔细想想这题不是找联通块啊。并不是上下左右能走过去就要计算在路径里的。每次路径必须保证数字越来越大才行的。

    - 改造了node，加入了一个长度属性。#2超时过不了（上面联通块的却能过#2 可笑）。开启O2优化后AC。

    - 现在研究一下如何不开启O2过#2

      未果

    ## [**P1433** 吃奶酪](https://www.luogu.org/problemnew/show/P1433)

    dfs顺利AC。也没做啥优化：

    - 仅仅是判断当前长度已经小于min就不往下了，剪枝。
    - 看题解有个人，是吧n个点两两访问的距离求出来存好了。这样在数据规模比较大的时候应该是有用的。不然很多时候两个点的距离要重复算。
      - 进一步优化这个思路。可以先不算出所有点两两间距离。dfs过程中算一个存一个，下次用到就直接取。用不到更省心。

    问题：

    - 第一次没AC：传入的点坐标也是double类型啊！谁说坐标就得是int!

    BFS就是队列。而我写DFS也觉得就是那么一套模板。总结下，每次我写基本都是这样：

    ​```cpp
    void dfs(a[i], 统计是否结束用的sum){
      	{
          //传进来做的必要处理
          
        }
      	if()//剪枝条件
            return;
      
      	if(){//遍历结束
          {
            //对解做出判断
          }
          return;
        }
      	for(i=0..n)
        {//继续dfs
          	if(!a[i].visited)//没被访问) 
            {
              	a[i].visited=1;//访问标记
               	dfs(a[i], sum+1);
              	{回档处理}
             		a[i].visited=0;
        }
    }

善于总结！加油。

P1074 靶形数独

License

Adopting CC BY-NC-SA 4.0 License Agreement

Share

快来参与讨论吧~