深搜和宽搜

DFS

DFS本质是使用栈进行搜索

void dfs(int x, int n)
    {
  			// 递归结束条件
        if(x == n)
        {
            g.push_back(temp);
            return;
        }

        for(int i = 0; i < n; i++)
        {
            if(col[i] == 0 && dg[x + i] == 0 && udg[n - x + i] == 0)
            {
              	// 向下搜索
                col[i] = dg[x + i] = udg[n - x + i] = 1;
                temp[x][i] = 'Q';
                dfs(x + 1, n);
              
              	//  回溯(还原)
                temp[x][i] = '.';
                col[i] = dg[x + i] = udg[n - x + i] = 0;
            }
        }
    }

对于需要回溯的深度优先搜索关键是 preorder 和 postorder 相呼应

BFS

BFS本质使用队列搜索

典型例题迷宫问题

AcWing 844. 走迷宫

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;

const int N = 110;

int map[N][N], st[N][N], dist[N][N];
int n,m;
int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0};

int main()
{
    
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> map[i][j];
    
    // 初始化BFS        
    memset(dist, -1, sizeof dist);
    queue<pair<int,int>> q;
    q.push({0,0});
    dist[0][0] = 0;
    
  	// 开始搜索
    while(q.size())
    {
      	// 出队
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        int t = dist[x][y];
      
      	// 遍历四个方向
        for(int i = 0; i < 4; i++)
            {
                int nx = x + dx[i], ny = y + dy[i];
          
          			// 上下左右没有出界,且有路径 , 没有被遍历过
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] == 0 && dist[nx][ny] == -1)
                {    
                  	// 入队并更新距离
                    q.push({nx,ny});
                    dist[nx][ny] = t + 1;
                }
            }
    }
    
  	// 输出最短路
    cout << dist[n - 1][m - 1];
    return 0;
}

状态转移BFS

AcWing 845. 八数码

假设每一次可以转移的状态路径权值为1,

我们用哈希表记录距离, 同时维护一个队列

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>
using namespace std;

int main()
{
    char n;
    string s;
    for(int i = 0; i < 9 ; i++) 
    {
        cin >> n;
        s += n;
    }

    // BFS
    string end = "12345678x";
    unordered_map<string, int> dist;
    queue<string> q;
    dist[s] = 0;
    q.push(s);

  	// 转移坐标
    int a[] = {1,0,-1,0}, b[] = {0,1,0,-1};

    while(q.size())
    {
      	// 出队
        auto s = q.front();
        q.pop();
        int distance = dist[s];
				
      	// 寻找x的位置
        int t = s.find('x');
      
      	// 一维坐标转移二维
        int x = t / 3, y = t % 3;
      
      	// 遍历相邻位置
        for(int i = 0; i < 4; i++)
        {
            int nx = x + a[i], ny = y + b[i];
          
          	// 边界检查
            if(nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
            {
              	// 还原坐标,并交换和x的位置
                swap(s[t],s[3*nx + ny]);
              
              	// 查询是否被遍历过
                if(!dist.count(s))
                {
                    dist[s] = distance + 1;
                    q.push(s);
                }
                swap(s[t],s[3*nx + ny]);
            }
        }
    }

    if(dist.count(end)) cout << dist[end];
    else cout << -1;
    return 0;
}