smart_robot

smart robot

题意

给定一个机器人，在一个二维平面N*N内移动，机器人可以移动到上下左右四个方向，然后每个位置上有一个个位数字。
可以随意选择初始位置，走任意的步数，根据所走的格子为一个数字，例如：走了3步，0，7，8三个格子，那么得到的数就是78 （不包含前导0）。
需要找到最小的不能走出的数字。

解题思路

因为 N 的范围为 50，下意识是个搜索题，直接 dfs 开搜。重要的是限制条件，其实可以直接猜一猜，我套用的 map ，根据时间复杂度，极限也就是走总共 5 个格子，所以控制在步数小于 5。
$50 50 （4 ^ 5) 10 ^ 6级别，再套个log，算是刚好没超时。$

然后如果不用 map，用数组去套用也可以，但尝试后，极限也就是多走一个格子，6个格子。

• 或许有时候也不能太依赖 STL？

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 60, inf = 1 << 30;

int g[N][N];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n;
int v[10000010];

void dfs(int x, int y, int count, int step) {
    if (step > 6) return ;
    for (int i = 0; i < 4; i ++ ) {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || b < 0 || a >= n || b >= n) continue;
        int c = count * 10 + g[a][b];
        v[c] = 1;
        dfs(a, b, c, step + 1);
    }
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < n; j ++ ) {
            cin >> g[i][j];
        }
    }
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < n; j ++ ) {
            v[g[i][j]] = 1;
            dfs(i, j, g[i][j], 1);
        }
    }
    for (int i = 0; i < 10000000; i ++ ) {
        if (!v[i]) {
            cout << i << endl;
            return ;
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}