标签：AC sum dfs queue 这题入队 luogu1 dfsbfs

普及练习场

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

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

DFS

P1219 八皇后

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

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

根本不用二维矩阵。

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

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

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

P1019 单词接龙

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

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

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

P1101 单词方阵

先说一下我的一些问题：

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

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

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

BFS

P1162 填涂颜色

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

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

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

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 字串变换

这个数据太***钻了：

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)坐标了啊。直接：

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

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

# 2 9 10 三个用例超时。#2是一个1000*1000的矩阵。10w条数据。我已经使用了记忆化搜索。实在想不到哪里可以优化了。
好像想出来我的问题了，我虽然使用了记忆化。但是我是把遍历到的联通块每个点的答案都存了起来。就是说我求出来了整个地图的解。看似读取快了。实际计算了很多不必须要的答案。应该只求输入里有的点就好。

P1126 机器人搬重物

拿到题：

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

Notice:

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

P1443 马的遍历

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

如果是c++则要：

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\)

记住这段代码：
```
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;//利用对称一次填充两个

细节：

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 滑雪

开始想错了思路。搞成了联通块。后来仔细想想这题不是找联通块啊。并不是上下左右能走过去就要计算在路径里的。每次路径必须保证数字越来越大才行的。
改造了node，加入了一个长度属性。#2超时过不了（上面联通块的却能过#2 可笑）。开启O2优化后AC。
现在研究一下如何不开启O2过#2

未果

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** 靶形数独](https://www.luogu.org/problemnew/show/P1074)

标签：AC,sum,dfs,queue,这题,入队,luogu1,dfsbfs
From： https://www.cnblogs.com/xuanshan/p/17551998.html

luogu1_dfsbfs

DFS