前言：

1.最短路问题和DP的关系：

最短路问题包含DP问题，DP问题可以看做最短路问题的特殊情况。

DP是没有环的最短路问题。

2.不是所有最短路问题都能用bfs来做。

只有所有边权重一样的时候才能用bfs做。

3.几种剪枝

最优性剪枝：当前路径一定可以判断出不如最优解

可行性剪枝：当前路径一定不合法

搜索

DFS

全排列

1680528086843

朴素版:简单递归

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
#include<iostream>
using namespace std ;
const int N = 10;

int n;
int path[N];
bool flag[N];

void dfs(int u)
{
    if(u==n){
        for(int i=0;i<n;i++){
            printf("%d",path[i]);
            if(i!=n-1) printf(" ");
            else printf("\n");
        }
    }
    for(int i = 1;i<=n;i++)
    {
        if(!flag[i])  //标志数组意味着在dfs过程中不会发生数据重复。
        {
            path[u] = i;
            flag[i] = true;
            dfs(u+1);
            //path[u] = 0;
            flag[i] = false;
        }
    }
    
}

int main(void)
{
    cin>>n;
    dfs(0); //下标从0开始（与数据从1开始 区分开）
}

位运算版：只是将朴素版的标志数组 以整数位运算的方式表示了。

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
#include <iostream>

using namespace std;

const int N = 10;

int n;
int path[N];

void dfs(int u, int state)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);
        puts("");

        return;
    }
    for (int i = 0; i < n; i ++ )
        if (!(state >> i & 1)) //查询第i位是不是0
        {
            path[u] = i + 1;
            dfs(u + 1, state + (1 << i));
        }
}

int main()
{
    scanf("%d", &n);

    dfs(0, 0);

    return 0;
}

state存的是当前i位的是否被填了的状态，但是state是一个整数，所以用state第i位是不是零存第i位的状态，查询第i位是不是零就是用!(state >> i & 1)

把具体的值加到path中去了之后，把下一个值递归到下一个dfs循环中，这时候把当前i左移一位加到state中就表示这一位已经被占用了。

n皇后

1680571430412

1680571452203

  • 把不放皇后看成0， 放皇后看成1，所有的情况就成了一个二叉树，每次都是向左（0）遍历，到了终点再回溯到能向右（1）遍历的节点开始向右遍历，是个二叉树的先序遍历算法。 —— acwing-user : Hsezr

这里需要注意，n皇后需要规避三种情况：横线，对角线，反对角线。

可以开辟三个数组，分别存储当前下标状态，是否已经存在皇后了。

横线好说，对角线如何处理呢？

col是Column（列）的缩写，dg是diagonal（对角）的缩写，反对角线为 udg

  • 设 udg 的坐标系方程为y=x+b，则b=y-x。

    1680571813508

    替换后即 b=u-i，防止出现负数，则加上n，则有b=u+n-i（其实b=n+i-u也可，目的是一个对角线能单独映射）

  • 设 dg 的方程为y=-x+b,b=y+x,替换后 b=i+u

    1680572333335

注意：图中行为 n , 列为col。 下面的代码中，我们设置行为 u ，列为 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
#include<iostream>
using namespace std ;
const int N = 20;
char graph[N][N];
bool col[N],dg[N],udg[N]; //标志数组，分别对应行、对角线和反对角线
int n;

void dfs(int u) //u : 到多少行了？
{
    if(u==n){
        for(int i=0;i<n;i++){
            cout<<graph[i]<<endl;
        }
        cout<<endl;
        return ;
    }
    for(int i=0;i<n;i++) //i 仅仅是多少列
    {
        if(!col[i]&&!dg[u+i]&&!udg[u+n-i]){ //y=x+b : b=y-x : b = u-i (规避负数+n)   | y=-x+b :b = x+y : b=u+i
            col[i]=dg[u+i]=udg[u+n-i] = true;
            graph[u][i] = 'Q';
            dfs(u+1);
            graph[u][i] = '.';
            col[i]=dg[u+i]=udg[u+n-i] = false;
        }
    }
}

int main(void)
{   
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            graph[i][j] = '.';
        }
    }
    dfs(0);
    
}

注意：开始我初始化N=10 ，有些样例是过不了的。对角线长度约1.414*10（根号2），经过测试，在1<=n<=9 的情况下， N=16 会WA掉n=9 ，N=17 就能 AC 。

复杂度：n*n!

朴素暴力做法

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
#include<iostream>
using namespace std ;
const int N = 20;
int n;
char g[N][N];
bool row[N],col[N],dg[N],udg[N]; //相比全排列多了一个行

void dfs(int x,int y, int s)
{
    if( s>n ) return;
    if( y==n ) { y=0; x++; }
    
    if(x==n){
        if(s==n){
            for(int i=0;i<n;i++){
                puts(g[i]);
            }
            puts("");
        }
        return ;
    }
    g[x][y] = '.';
    dfs(x, y + 1, s);

    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        g[x][y] = 'Q';
        dfs(x, y + 1, s + 1);
        g[x][y] = '.';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }
}


int main(void)
{
    cin>>n;
    dfs(0,0,0); // 参数1,2分别为x，y。 参数3为 当前有几个皇后
}

复杂度：2^(n^2)

为什么第一种写法不用考虑行，而第二种则要考虑行？

  1. 第一种是我们已经知道一行只能放一个皇后才这么写，第二种是更朴素的想法一个格子一个格子往下走。

  2. 这里你还可以参照，第一种写法的状态参数是if : u==n ，第二种写法则是

    1
    2
    3
    4
    5
    6
    7
    if( s>n ) return;
    if( y==n ) { y=0; x++; }
       
    if(x==n){
        if(s==n){
            ...
        }

    简单来说：

    • 全排列写法是一行一行往下走，一旦放置皇后就下一行。

    • 朴素写法是一格一格移动着走。

    前者不需要考虑同一行里是否发生重复皇后，后者则需要考虑。

全球变暖

你有一张某海域 NxN 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：

…….

.##….

.##….

….##.

..####.

…###.

…….

其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

…….

…….

…….

…….

….#..

…….

…….

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入描述

第一行包含一个整数 N* (1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。、

输出一个整数表示答案。

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
#include<iostream>
using namespace std;
const int N = 1010;
int n;
bool flag;
int res;
bool vis[N][N];
char m[N][N];
int h[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int x,int y)
{
    vis[x][y]= true;
    if(m[x][y]=='.')  return ;

    bool temp = true;


    for(int i=0;i<4;i++)
    {
        int tx = x+h[i][0] , ty = y+h[i][1];
        if(m[tx][ty]=='.') temp = false;
        if(!vis[tx][ty]) dfs(tx,ty);
    }
     if(temp) flag = true;
    

}
int main(void)
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>m[i][j];
        }
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!vis[i][j]&&m[i][j]=='#'){
                flag = false;
                dfs(i,j);
                if(!flag) res++;            
            } 

        }
    }
    cout<<res;
    
}

BFS

走迷宫

1680519080392

1680519093320

普通版本：

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
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N], d[N][N];

int bfs()
{
    queue<PII> q;

    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0, 0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];

            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }

    return d[n - 1][m - 1];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}

手搓队列的朴素版本

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
//朴素版本
#include<iostream>
#include<cstring>
using namespace std ;
const int N = 110;

typedef pair<int,int> PII;
int g[N][N];
int d[N][N];
int n,m;
//手搓队列queue
PII q[N*N];

int bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof(d));
    
    q[0]={0,0};
    d[0][0] = 0;
    
    int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
    
    while(hh<=tt)
    {
        auto t = q[hh++];

        for(int i=0;i<4;i++){
            int tx = t.first +dir[i][0],ty = t.second+dir[i][1];
            if(tx>=0&&tx<n&&ty>=0&&ty<m&&g[tx][ty]==0&&d[tx][ty]==-1){
                q[++tt] = {tx,ty};
                d[tx][ty] = d[t.first][t.second]+1;
            }
        }
    }
    return d[n-1][m-1];
}

int main(void)
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&g[i][j]);
        }
    }
    cout<<bfs();
    
    return 0;
}

八数码问题

1680509275781

这里搜索需要处理两个点：

1.状态表示。 —— queue队列

2.状态之间的距离如何记录。 —— dist数组

答案：

1.将二维网格降维成一个字符串来表示，如上面1~8的示例，可以用字符串“123x46758” 来表示。

即queue

2.用C++里的哈希表STL ： unordered_map<string,int>

最后一个问题：状态转移

①复原状态：将一维字符串还原成二维（至少先从脑子里）

②更新状态：枚举空格上下左右移动后的状态。

③存入队列：移动后把二维结果恢复成字符串，存入bfs队列。

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
#include<iostream>
#include<queue>
#include<algorithm>
#include<unordered_map>
#include<string>
using namespace std ;
#define NUM 3

queue<string> q;
unordered_map<string,int> d; //dist 

int bfs(string state)
{
    string end = "12345678x";  //预定结果 了
    q.push(state);
    d[state] = 0;
    int direct[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    
    
    while(q.size())
    {
        //队列操作
        string str = q.front();
        q.pop();
        //判断是否结束
        if(str == end) return d[str];
        
        //枚举前的初始化
        int distance = d[str];
        int key = str.find('x');
        int x = key/NUM, y = key%NUM; 
        
        //更新数据
        for(int i=0;i<4;i++)
        {
            int tx = x + direct[i][0], ty = y + direct[i][1];
            if(tx>=0&&tx<NUM&&ty>=0&&ty<NUM)
            {
                swap(str[key],str[tx*NUM+ty]);//交换完成，更新状态
                if(!d[str])
                {
                    d[str] = distance +1;
                    q.push(str);
                }
                swap(str[key],str[tx*NUM+ty]);//更新完成，复原状态
            }
            
        }
    }
    return -1; //枚举完成，没有找到结果，返回-1。
}

int main(void)
{
    string start;
    for(int i=0;i<9;i++){
        char s[2];
        cin>>s;
        start += *s;
    }
    cout<<bfs(start);
    
return 0;
    
}

迷宫

问题描述

这天, 小明在玩迷宫游戏。

迷宫为一个 n x n 的网格图, 小明可以在格子中移动, 左上角为 (1,1)(1,1), 右 下角 (n, n)(n,n) 为终点。迷宫中除了可以向上下左右四个方向移动一格以外, 还有 m 个双向传送门可以使用, 传送门可以连接两个任意格子。

假如小明处在格子(x1,y1), 同时有一个传送门连接了格子 (x1,y1) 和 (x2,y2), 那么小明既可以花费 1 的步数向上下左右四个方向之一走一格 (不能 越过边界), 也可以花费 1 的步数通过传送门走到格子 (x2,y2) 去。

而对于同一个迷宫, 小明每次进入的初始格子是在这n*×n 个格子中均匀随 机的 (当然运气好可以直接随机到终点), 他想知道从初始格子走到终点的最短 步数的期望值是多少。

输入格式

输入共 1+m1+m 行, 第一行为两个正整数 n, mn,m 。

后面 mm 行, 每行四个正整数 x1,y1,x2,y2 表示第 ii 个传送门连接的两个格子坐标。

输出格式

输出共一行, 一个浮点数表示答案 (请保留两位小数)。

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
#include <iostream>
#include<deque>
using namespace std;
const int N = 25;
int a[N];
int b[N];
int vis[N][N];
int n;
int dis[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
deque<int> d;
bool dfs(int x,int y)
{
  if(x==n-1&&y==n-1){
    for(int i=0;i<n;i++){
      if(a[i]||b[i])
        return false;
    }
    return true;
  }

  for(int i=0;i<4;i++){
    int tx = x+dis[i][0],ty = y+dis[i][1];
    if(tx>=0&&ty>=0&&tx<n&&ty<n&&!vis[tx][ty]&&(a[ty])&&(b[tx]))
    {
      a[ty]--;b[tx]--;
      vis[tx][ty]=1;
      d.push_back(tx*n+ty);
      if(dfs(tx,ty)) return true;
      a[ty]++;b[tx]++;
      vis[tx][ty]=0;
      d.pop_back();
    }
    else continue;
  }
  return false;

}
int main()
{
  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++) cin>>b[i];
  d.push_back(0);
  vis[0][0]=1;
  a[0]--;b[0]--;

  if(dfs(0,0)){
    for(auto it = d.begin();it!=d.end();it++){
      cout<<*it<<" ";
    }
  }
  return 0;
}

快来参与讨论吧~