题目链接

Curling 2.0 POJ - 3009

思路

dfs回溯，因为有4个方向可以走，最多可以走10步，每步最多走20格，当然实际情况，远远达不到这个时间上限。

时间复杂度

$$ 每组O(max(N, M) * 4 ^ {10}) $$

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAXN = 25;  
int n, m;

int a[MAXN][MAXN];
int sx, sy;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int ans;

bool check(int x, int y) {
    if (1 <= x && x <= n && 1 <= y && y <= m) {
        return true;
    } else {
        return false;
    }
}

void dfs(int x, int y, int step) {

    if (step >= ans) {
        return;
    }
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];

        while (check(xx, yy) && a[xx][yy] == 0) {
            xx += dx[i];
            yy += dy[i];
        }
        if (check(xx, yy) && a[xx][yy] == 3) {
            ans = min(step, ans);
            continue;
        }
        if (xx == x + dx[i] && yy == y + dy[i]) {
            continue;
        }
        int px = xx - dx[i];
        int py = yy - dy[i];
        if (check(xx, yy) && a[xx][yy] == 1) {
            a[xx][yy] = 0;
            dfs(px, py, step + 1);
            a[xx][yy] = 1;
        }
    }

}

int main() {
    while (scanf("%d%d", &m, &n), n + m) {

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);// don't forget &
                int cur = a[i][j];
                if (cur == 2) {
                    sx = i;
                    sy = j;
                }
            }
        }

        ans = 11;
        a[sx][sy] = 0;
        dfs(sx, sy, 1);
        printf("%d\n", ans == 11 ? -1 : ans);

    }
    return 0;
}