(DFS) Depth-First Search入门

Depth-First Search简称DFS，深度优先搜索。 深度优先，优先在于深度，尽量往最深处走。 原理:从某一节点开始走，若遇到分支，选择某条路冲到底，遇到分支就随便选只管冲冲冲，直到冲到底再无选择，然后按原路返回如果再遇到分支且有没走过的路，依然冲冲冲。直到全部都搜索完。 DFS 就如《葬送的芙莉莲》中芙莉莲与勇者探索迷宫的精神，攻略迷宫要将迷宫全部探索完才是迷宫寻宝的真正魅力！！！

如题 【入门】扫地机器人 我们根据题意可以知道n与m的值为2~9，所以二维数组可以开a[11][11]即使nm为最大时依然可以在周围留一圈0，反正判断时越界等问题。 根据题意我们需要设置一个判断规则: 按右下左上 的优先级进行判断。

下面给出AC代码

#include<iostream>
#include<vector>
using namespace std;
const int N = 11;//因为n和m是2~9的数所以周围留下了一圈

int n,m;
vector<vector<int> >a(N,vector<int>(N, 0));

//递归深搜
void dfs(int x, int y, int k)//为（x,y）赋k值
{
    a[x][y] = k;
    //按照题目要求的右下左上的顺序依次设计判断x与y的加减依次对应了右下左上
    if(y + 1 <= m && a[x][y + 1] == 0){
        dfs(x, y + 1, k + 1);
    }else if(x + 1 <= n && a[x + 1][y] == 0){
        dfs(x + 1, y, k + 1);
    }else if(y - 1 > 0 && a[x][y - 1] == 0){
        dfs(x, y - 1, k + 1);
    }else if(x - 1 > 0 && a[x - 1][y] == 0){
        dfs(x - 1, y, k + 1);
    }
}

int main()
{
    std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //输入行列
    cin >> n >> m;
    //赋初值
    dfs(1, 1, 1);//依题意设计函数dfs为(1,1)赋值为1,dfs函数赋值的点是我们搜索开始的最初点
    //输出
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            printf("%3d",a[i][j]);
        }
        printf("\n");
    }
}