本周学习总结

本周所看的学习的内容，以搜索题目为中心，看过一些题目之后，我对于搜索的理解又加深了一步，我看到了许多搜索的新题型，每一个都值得我去细细的钻研。

比如，全排列问题：全排列问题 - 洛谷

#include
#include 
using namespace std;
int a[10];
int main()
{
	int n, i, j = 1, k;
	cin >> n;
	for (i = 1; i <= n; i++)
	{
		a[i] = n - i + 1; j *= i;
	}
	for (i = 1; i <= j; i++)
	{
		next_permutation(a + 1, a + n + 1);
		for (k = 1; k <= n; k++)
			cout << "    " << a[k];//排一次输出一次
		cout << endl;
	}
	return 0;
}

这道题最开始我是没有头绪的，知道我看到题解，才知道这道题非常的简单，它的核心就在于头文件中的next_permutation（start,end）函数，有人称它为全排列函数或者字典排函数，它的作用也很明显，就是对于一堆数，进行全排列，我们只需要去把每一种情况打印下来就好；

还有一种情况是我再翻博客的时候偶然间看到的，觉得也很好，就摘了过来，具体的文章可阅读https://blog.csdn.net/feiwatellily/article/details/113499015?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164954896016780264066636%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164954896016780264066636&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-2-113499015.142^v7^pc_search_result_cache,157^v4^control&utm_term=搜索&spm=1018.2226.3001.4187

他的全排列问题中提到了用深搜的方法做，具体代码如下：
 

#include 
#include 

using namespace std;

int arr[1000];
int book[1000]; //用来表示此数字有没有被用过，初始化为0表示没用过
int n;
void dfs(int step)//step表示当前处于第step个盒子
{
    if(step==n+1) //先写退出条件，让答案输出
    {
        for(int i  = 1; i <= n; i++) cout<< arr[i] << ' ';
        cout << endl;
        return;  //此题目一定要写，不返回的话会一直搜索下去然后卡死
    }//让它返回到第n个盒子继续处理
    for(int i = 1; i <= n; i++)
    {//遍历盒子如果book[i]显示为0的话表示没用过，可放到盒子里去
        if(!book[i])
        {
            book[i] = 1; //先让他标记为1表示用过了
            arr[step] = i;//放到盒子里去
            dfs(step+1);//继续搜索下一个地方
            book[i] = 0;//消除之前的标记
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
    return 0;
}

他的做法是将1~n的数看成n个小球，将他们放到n个盒子里（他们的位置代表盒子的编号），对于全排列来说，一个盒子随机放一个球，且放过的球和盒子要去标记，防止重复使用。

这个揭发要注意的一点是回溯，及每一个排列结果得到后，作为标记的数组book[]要重新归零。

搜索还可以处理背包问题：

这道题型我在上一篇博客中已经做出解释，这里就不细讲了，只需记住：

• 就是这个物品到底装不装，每个物品只有一件，你的选择就是这一件到底装还是不装。
  

  
  

• 状态转移方程：(从大到小进行枚举），即可。
  

  
  

 还有就是01迷宫问题：https://www.luogu.com.cn/problem/P1141

#include
#include
#include
using namespace std;
int n, m, ans[100002], x, y, f[1002][1002];
char s[1002][1002];
void dfs(int r, int c, int z, int lll) {
    if (r < 0 || r >= n || c < 0 || c >= n || f[r][c] != -1 || s[r][c] - '0' != z)return;
    f[r][c] = lll; ans[lll]++;
    dfs(r - 1, c, !z, lll); dfs(r + 1, c, !z, lll); dfs(r, c - 1, !z, lll); dfs(r, c + 1, !z, lll);
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> s[i];
    memset(f, -1, sizeof(f));
    for (int i = 0; i < m; i++)
    {
        cin>>x>>y; x--; y--;
        if (f[x][y] == -1)dfs(x, y, s[x][y] - '0', i); else ans[i] = ans[f[x][y]];
    }
    for (int i = 0; i < m; i++)
        cout << ans[i];
    return 0;
}

里面的变量r和c分别表示点的横纵坐标，我第一次写代码的时候就没有注意这个问题，所以一直不通过，其次就是递归了，对与一个点，把他的上下左右每一点都走一遍，最终得出结果。

以及八皇后问题：https://www.luogu.com.cn/problem/P1219

玩过国际象棋的都知道，皇后是可以吃掉自己的上下左右以及与自己处在同一对角线的

棋子，那么，再一个nXn的棋盘上，如何摆放才会让n个皇后和平相处？

#include
#include
#include
#include
using namespace std;
int a[100], b[100], c[100], d[100];
//a数组表示的是行；
//b数组表示的是列；
//c表示的是左下到右上的对角线；
//d表示的是左上到右下的对角线；
int total;//总数:记录解的总数
int n;//输入的数，即N*N的格子，全局变量，搜索中要用
int print()
{
    if (total <= 2)//保证只输出前三个解，如果解超出三个就不再输出，但后面的total还需要继续叠加
    {
        for (int k = 1; k <= n; k++)
            cout << a[k] << " ";//for语句输出
        cout << endl;
    }
    total++;//total既是总数，也是前三个排列的判断
}
void queen(int i)//搜索与回溯主体
{
    if (i > n)
    {
        print();//输出函数，自己写的
        return;
    }
    else
    {
        for (int j = 1; j <= n; j++)//尝试可能的位置
        {
            if ((!b[j]) && (!c[i + j]) && (!d[i - j + n]))//如果没有皇后占领，执行以下程序
            {
                a[i] = j;//标记i排是第j个
                b[j] = 1;//宣布占领纵列
                c[i + j] = 1;
                d[i - j + n] = 1;
                //宣布占领两条对角线
                queen(i + 1);//进一步搜索，下一个皇后
                b[j] = 0;
                c[i + j] = 0;
                d[i - j + n] = 0;
                //（回到上一步）清除标记
            }
        }
    }
}
int main()
{
    cin >> n;//输入N*N网格，n已在全局中定义
    queen(1);//第一个皇后
    cout << total;//输出可能的总数
    return 0;
}

本道题最重要的就是记录下皇后占领的格子（打标记的思想），通过此判断下一个皇后是否可以在某个位置，如果可以，则继续搜索下一个皇后可以在的位置，如果不行，则清除标记回到上一步，继续搜索；

搜索能解决的问题还有很多，背包问题，迷宫问题，马的遍历，最短路径，还有近期碰到的新题

如https://www.luogu.com.cn/problem/P1135（奇怪的迷宫）。

还有很多题我仍在理解中，但是对于搜索算法的感悟我想在这里说一下：

对于dfs和bfs，他们可以用来解决数独问题，部分和问题，最短路径问题，遍历问题，n皇后问题，素数环问题，且由于搜索的时间复杂度较高，在代码编写过程中可能会用到剪枝。

对于深搜，他经常会用到回溯，即一条路走不通时，将其归零，重新选择下一条路径。

其实相比前一周，我感觉我有提高，但是还是存在许多尚未解决的问题，比如剪枝，我虽然知道它是什么原理，但是却写不出来代码，这是下一步我要去着重练习的。