深度优先搜索和广度优先搜索

深度优先搜索和广度优先搜索。

深度优先搜索

以输出排列数为例，主要进行状态的转移。

输出排列数https://www.acwing.com/activity/content/problem/content/905/

#include<bits/stdc++.h>
using namespace std;
const int N =10;
int path[N];
vector<bool>vis(N);
int n;
void dfs(int u)//n表示要搜索的位数。
{
    if(u==n)//搜索到了第n位
    {
        for(int i=0;i<n;i++)cout<<path[i]<<" ";//对排列进行输出。
        cout<<endl;
    }
    else
    {
        for(int i=1;i<=n;i++)//对所有数进行遍历。
        {
            if(!vis[i])//如果数没有被访问过，即数没有被用在排列中。
            {
                path[u] = i;//进行排列
                vis[i] = true;//更新数的选择状态。
                dfs(u+1);//对下一位进行搜索
                vis[i] = false;//回溯之前的状态。
            }
        }
    }
}
int main(void)
{
    cin>>n;
    dfs(0);
}

dfs也常用来进行暴力搜索，再数据量较小的情况下，对所有情况取值进行枚举进行搜索，通常根据题目情况配合回溯剪枝减小题目复杂度。
例题：
https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
https://leetcode.cn/problems/find-minimum-time-to-finish-all-jobs/
https://leetcode.cn/problems/matchsticks-to-square/
该三道题的代码思路大致相同，都是均分后，暴搜看能否搜索到正好满足的情况。
常用剪枝。
在搜索前进行情况判断，若已经不满足则不再进行后续搜索。

if(conditon) dfs();

若回溯后，该组为值为0,后续无论如何搜索也不能得到有意义的答案，直接返回，不进行后续搜索。

if(sun[i]==0)return;

代码：

class Solution {
public:
    vector<int>sum;
    int k;
    vector<int>jobs;
    int ans;
    void dfs(int idx)
    {
        if(idx==jobs.size())
        {
            int mx =0;
            for(int i=0;i<k;i++)
            {
                mx =max(mx,sum[i]);
            }
            ans =min(ans,mx);
            return ;
        }
        for(int i=0;i<k;i++)
        {
            sum[i]+=jobs[idx];
            if(sum[i]<ans)//剪枝
            {
                dfs(idx+1);
            }
            sum[i]-=jobs[idx];
            if(sum[i]==0)//剪枝
            {
                return;
            }
        }
    }
    int minimumTimeRequired(vector<int>& jobs, int k) {
        vector<int>sum(12,0);
        this->sum = sum;
        this->k = k;
        sort(jobs.begin(),jobs.end());
        this->jobs =jobs;
        ans =1e9;
        dfs(0);
        return ans;
    }
};

n-皇后问题

https://www.acwing.com/activity/content/problem/content/906/

#include<bits/stdc++.h>
using namespace std;
const int N =20;
bool col[N],dg[N],udg[N];//分别标记列，对角和反对角线
int n;
char g[N][N];//存储图
void dfs(int u)//函数按行进行枚举搜索。
{
    if(u==n)//如果搜索到第n行。
    {
        for(int i=0;i<n;i++)//输出可能的结果
        {
            for(int j=0;j<n;j++)
            {
                cout<<g[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
    }
    //枚举第u行,第i列
    for(int i=0;i<n;i++)
    {
        if(!col[i] && !dg[u+i] && !udg[n-u+i])//如果该列，该对角线，该反对角线都没有皇后，则可以放入皇后
        {
            g[u][i] = 'Q';//放入皇后
	    //更新状态	
            col[i] =true;
            dg[u+i] = true;
            udg[n-u+i] = true;
            dfs(u+1);//对下一行进行搜索
	    //回溯
            col[i] =false;
            dg[u+i] = false;
            udg[n-u+i] = false;
            g[u][i]='.';
        }
    }
}
int main(void)
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            g[i][j]='.';
        }
    }
    dfs(0);
    
    
}

在搜索路径时，应注意剪纸枝来提算法效率，有时需要多次剪枝。
例：https://leetcode-cn.com/problems/check-if-there-is-a-valid-parentheses-string-path/
代码

class Solution {
public:
    int m,n,c;//c表示当前括号状态，c>=0均为合法状态
    bool flag;
    bool vis[101][101][201];
    bool dfs(vector<vector<char>>& grid,int x,int y)
    {
        //cout<<x<<" "<<y<<endl;
        if (c > m - x + n - y - 1) return false;//当剩下的路径都不足以抵消c时，必然不成立，返回，剪枝
        if(x==m-1 && y==n-1 && c==0)//搜索成功状态。
        {
            flag =true;
            return true;
        }
        if(vis[x][y][c]) return false;//由x,y,c确定的唯一状态已被搜索过，返回，剪枝
        vis[x][y][c]=1;
        if((x+1)<m && !flag)
        {
            if(grid[x+1][y]=='(' && !flag)//若已有路径搜索到终点，返回，剪枝，下面分支皆是该策略。
            {
                ++c;
                if(c>=0)
                {
                    dfs(grid,x+1,y);
                }
                --c;//回溯
            }
            else if(grid[x+1][y]==')' && !flag)
            {
                --c;
                if(c>=0)
                {
                    dfs(grid,x+1,y);
                }
                ++c;
            }
        }
        if((y+1)<n && !flag)
        {
            if(grid[x][y+1]=='(' && !flag)
            {
                ++c;
                if(c>=0)
                {
                    dfs(grid,x,y+1);
                }
                --c;
            }
            else if(grid[x][y+1]==')' && !flag)
            {
                --c;
                if(c>=0 && !flag)
                {
                     dfs(grid,x,y+1);
                }
                ++c;
            }
        }
        return false;
    }
    bool hasValidPath(vector<vector<char>>& grid) {
        flag =false;
        m=grid.size();
        n=grid[0].size();
        if(grid[0][0]==')' || grid[m-1][n-1]=='(' || (m+n)%2==0)
        {
            return false;//剪枝，起始为')'，终点为'('。均不满足要求。
      //此外，从左上角走到右下角，走过的长度为m+n-1,要求括号闭合，再次剪枝
        }
        memset(vis,0,sizeof(vis));
        c=1;
        dfs(grid,0,0);
        if(flag)
        {
            return true;
        }
        else 
        {
            return false;
        }
    }
};

广度优先搜索

广度优先搜索一般都借助队列这一数据结构，有一些固定的模式。
走迷宫。
https://www.acwing.com/activity/content/problem/content/907/

#include<bits/stdc++.h>
using namespace std;
const int N =105;
int a[N][N];
int dis[N][N];//存储到起点的距离
//设置搜索方向
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int main(void)
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];
        }
    }
    queue<pair<int,int>>q;
    q.push({0,0});//放入起点
    memset(dis,-1,sizeof(dis));
    while(!q.empty())
    {
        auto [x,y] = q.front();//弹出要搜索的点
        q.pop();
        for(int i=0;i<4;i++)//对四个方向进行搜索
        {
                int nx =x+dx[i];
                int ny =y+dy[i];
                if(nx>=0 && nx<n&&ny>=0 && ny<m && a[nx][ny]==0 && dis[nx][ny]==-1)//判断是否越界，为墙，还没有搜索过
                {
                    q.push({nx,ny});//放入队列，等待搜索
                    dis[nx][ny] = dis[x][y]+1;//更新距离。
                }
        }   
    }
    cout<<dis[n-1][m-1]+1;
    
}

八数码
https://www.acwing.com/problem/content/847/

#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int>d;//映射字符串状态到输入状态的距离
queue<string>q;//搜索的队列
int dx[4]={0,0,1,-1};//搜索方向
int dy[4]={1,-1,0,0};
int bfs(string start)
{
    //cout<<1<<endl;
    q.push(start);//将开始的搜索状态放入。
    d[start]=0;
    string endstate = "12345678x";//最终的搜索状态
    while(!q.empty())
    {
        string t= q.front();
        q.pop();
        int dis =d[t];
        if(t==endstate) //如果搜索到了最终状态，返回距离
        {
            return  dis;
        }
        int k = t.find('x');//找到x的位置
        int x = k/3;//转移到2维上
        int y = k%3;//转移到2维上
        for(int i=0;i<4;i++)//在二维上进行搜索
        {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx>=0 && nx<3 && ny>=0 && ny<3)//判断是否越界
            {
                swap(t[k],t[3*nx+ny]);//向下一个状态进行移动
                if(!d.count(t))//如果还没有搜索到
                {
                    d[t] =dis+1;//更新距离
                    q.push(t);//进行下一步搜索
                }
                swap(t[3*nx+ny],t[k]);//回溯。
            }
        }
    }
    return -1;
    
    
}
int main(void)
{
    string start;
    for(int i=0;i<9;i++)
    {
        char c;
        cin>>c;
        start+=c;
    }
    //cout<<"start:"<<start<<endl;
    cout<<bfs(start)<<endl;
}