【搜索 - 牛客第一节课后笔记】

题目索引

1. n 皇后进阶版
2. 走马
3. 迷宫问题
4. 数独挑战
5. 持续更新中…

DFS

n 皇后进阶版

1.n 皇后进阶版

1. 主对角线: 会发现该条对角线的值都是 ( i - j ) -> 但是会有负数, 但是数组没有负数小标, 故将它 + n投影过去

2. 副对角线: 会发现该条线上所有的值都是 (i + j)

3. 然后就是 col
   

->故我们设置三个标记数组: col[N], zd[N2], fd[N2]

---

4. 输出: 不同点, 此次记录的是第 i 行的皇后放在了那一列
5. 最后输出就是类似于游戏 canvas 的输出方式

->回忆起实训的时候做的游戏, 用二维数组构建画布

---

6. 注意我们遍历的顺序是从第一列到最后一列, 所以尝试的时候有顺序

if(dep > n)
    {
        for(int i = 1; i <= n; i ++ ) // 枚举第几个皇后
        {
            for(int j = 1; j <= n; j ++ ) // 第 i 个皇后在第几列
            {
                if(a[i] == j) cout << 'Q'; // 注意这里的写法 是 a[i] == j
                else cout << '.';
            }
            cout << endl;
        }
        cout << endl;
        
        return ;
    }

新的认识:就是一个 dfs return是为了形成一条链, 如果该层不满足, 那么仅仅只是执行完本层的 dfs 不会陷入死循环

#include 

using namespace std;

int a[6];

void dfs(int x)
{
    if(x == 2) {cout << "YES"; return ;}
    
    for(int i = 2; i < 5; i++ ) a[i] = i;
    
}

int main()
{
    dfs(3);
    
    for(int i = 2; i < 5;  i ++ ) cout << a[i] <<endl;
    
}

n皇后的正解 -> 可以更加灵活的写dfs

#include 

using namespace std;

const int n = 4;

int a[n];
int col[14], zd[30], fd[30];

void dfs(int dep)
{
    if(dep > n)
    {
        for(int i = 1; i <= n; i ++ ) // 枚举第几个皇后
        {
            for(int j = 1; j <= n; j ++ ) // 第 i 个皇后在第几列
            {
                if(a[i] == j) cout << 'Q'; // 注意这里的写法 是 a[i] == j
                else cout << '.';
            }
            cout << endl;
        }
        cout << endl;
        
        return ;
    }
    
    for(int i = 1; i <= n; i ++ )
    {
        if(col[i] == 0 && zd[dep - i + n] == 0 && fd[dep + i] == 0)
        {
            a[dep] = i;
            col[i] = 1; zd[dep - i + n] = 1; fd[dep + i] = 1;
            dfs(dep + 1);
            col[i] = 0; zd[dep - i + n] = 0; fd[dep + i] = 0;
        }
    }
}

int main()
{
    dfs(1);
}

走马

1. 走马

题目大意: 马在(1, 1)的位置, 问遍历完 5*5 的棋盘所有的方法

1. 意外发现: 如果是2, 3, 4 没有解, 而 6, 7等等会超时

2. 新的: vis -> vistor (一个访问数组)

3. 新的偏移量表达方式: int dir[8][2], 偏移量可以根据 y = x, 只看一边的坐标, 然后对称写 4 -> -2, -1, -1, -2 | -2, 1, 1, -2, | -1, 2, 2, -1| 1, 2, 2, 1|

4. 输出方式: 用 vis 达到两个目的, 第一 看看是否被访问, 第二看看到这个点的距离, 一举两得

---

#include 

using namespace std;

const int N = 10;

int n = 5;

int vis[N][N];
int dir[8][2] = {{-2, -1}, {-1, -2}, {-2, 1}, {1, -2}, {-1, 2}, {2, -1}, {1, 2}, {2, 1}};

void dfs(int dep, int x, int y)
{
    if(dep == n*n)
    {
        for(int i = 1; i <= n; i ++ )
        {
            for(int j = 1; j <= n; j ++ )
            {
                printf("%4d", vis[i][j]);
            }
            cout << endl;
        }
        cout << endl;
    }
    
    for(int i = 0; i < 8; i ++ )
    {
        int dx = x + dir[i][0];
        int dy = y + dir[i][1];
        
        if(dx <= 0 || dx > n || dy <= 0 || dy > n) continue;
        if(vis[dx][dy] != 0) continue;
        vis[dx][dy] = dep + 1;
        dfs(dep + 1, dx, dy);
        vis[dx][dy] = 0;
    }
}

int main()
{
    vis[1][1] = 1;
    dfs(1, 1, 1);
}

BFS

迷宫问题

3. 迷宫问题

题目大意: 从起点走到终点的最短路

1. 新的不用 pair 的方法: 使用特殊的下标存储方式 -> 如上图所示
2. 同样也是偏移量的记忆: 沿着 y = x 方向只用看两个点儿
3. 然后就是 inmap 和 check 函数 更好的封装了语义

#include 
#define gg exit(0);

using namespace std;

const int N = 20;
const int dir[4][2] = {0, -1, -1, 0, 1, 0, 0, 1};

int n, m;
queue<int> q;
int dist[N][N];
int a[N][N];

bool inmap(int x, int y)
{
    if(x >= 0 && y >= 0 && x < n && y < n) return 1;
    return 0;
}

bool check(int x, int y)
{
    if(dist[x][y] == -1 && a[x][y] == 1) return 1;
    return 0;
}

void bfs(int x, int y)
{
    // 初始化
    memset(dist, -1, sizeof dist);
    
    q.push(x*m +y);
    dist[x][y] = 0;
    
    // 具象化
    while(q.size())
    {
        int tmp = q.front();
        q.pop();
        int x = tmp / m, y = tmp % m;
        
        for(int i = 0; i < 4; i ++ )
        {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            
            if(inmap(dx, dy) && check(dx, dy))
            {
                q.push(dx * m + dy);
                dist[dy][dy] = dist[x][y] + 1;
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++ )
        {
            cin >> a[i][j];
        }
        
        
    bfs(0, 0);
    
    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < n; j ++ )
            cout << dist[i][j] <<' ';
        cout <<endl;
    }
    
    return 0;
}

#include 

using namespace std;


int cnt = 0;
int a[10][10];
int h[12][12], l[12][12];
int x[12][12]; // 第一行的[1, 9] 是否用过
const int xiao[10][10] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
                    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3}, 
                    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3}, 
                    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6}, 
                    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6}, 
                    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
                    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
                    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
                    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}};

struct ty
{
    int x, y;
}kong[90];

void print()
{
    for(int i = 1; i <= 9; i ++ )
    {
        for(int j = 1; j <= 9; j ++ )
            cout << a[i][j] << ' ';
        cout << endl;
    }
}

void dfs(int dep)
{
    if(dep > cnt)
    {
        print();
        return ;
    }
    
    int xx = kong[dep].x, yy = kong[dep].y;
    int k = xiao[xx][yy];
    for(int i = 1; i <= 9; i ++ )
    {
        if(h[xx][i] == 0 && l[yy][i] == 0 && x[k][i] == 0)
        {
            a[xx][yy] = i;
            h[xx][i] = 1; l[yy][i] = 1; x[k][i] = 1;
            dfs(dep + 1);
            h[xx][i] = 0; l[yy][i] = 0; x[k][i] = 0;
        }
    }
}

int main()
{
    for(int i = 1; i <= 9; i ++ )
        for(int j = 1; j <= 9 ; j ++ )
        {
            cin >> a[i][j];
            if(a[i][j] == 0) kong[++cnt] = {i, j};
            else
            {
                int t = a[i][j];
                h[i][t] = 1, l[j][t] = 1, x[xiao[i][j]][t] = 1;
            }
        }
            
    dfs(1);
}