Grid Paths

描述

在 的方格中，给出一个不完全的路径序列，已知方位用 表示，未知方位用 表示。
求所有可能的，从左上角到左下角，且经过所有格子正好一次的路径数量。

分析

经典的搜索回溯问题，但是涉及到一些比较高级的剪枝技巧。
书 Competitive Programmer’s Handbook 的 页，详细讲了几种剪枝优化策略，强烈推荐去看一看，这份代码也是基于此完成的。

代码

#include <cstdio>

bool g[10][10];
char s[55];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int k, ans;

void init() {
    for (int i = 0; i <= 8; i++) g[i][0] = g[i][8] = true;
    for (int j = 1; j <= 7; j++) g[0][j] = g[8][j] = true;
    g[1][1] = true;

    for (int i = 0; i < 48; i++) {
        if (s[i] == 'R') s[i] = 0;
        else if (s[i] == 'D') s[i] = 1;
        else if (s[i] == 'L') s[i] = 2;
        else if (s[i] == 'U') s[i] = 3;
    }
}

bool check(int x, int y) {
    if (k == 0) return false;
    int id = s[k - 1];
    int x1 = x + dir[id][0];
    int y1 = y + dir[id][1];

    int x2 = x + dir[(id + 1) % 4][0];
    int y2 = y + dir[(id + 1) % 4][1];
    int x3 = x + dir[(id + 3) % 4][0];
    int y3 = y + dir[(id + 3) % 4][1];
    return g[x1][y1] && !g[x2][y2] && !g[x3][y3];
}

void dfs(int x, int y) {
    if (k == 48) {
        ans += (x == 7 && y == 1);
        return;
    }
    if (x == 7 && y == 1) return;

    if (s[k] != '?') {
        int _x = x + dir[s[k]][0];
        int _y = y + dir[s[k]][1];

        if (!g[_x][_y]) {
            g[_x][_y] = true;
            k++;
            dfs(_x, _y);
            k--;
            g[_x][_y] = false;
        }
        return;
    }

    if (check(x, y)) return;
    for (int i = 0; i < 4; i++) {
        int _x = x + dir[i][0];
        int _y = y + dir[i][1];
        if (g[_x][_y]) continue;

        g[_x][_y] = true;
        s[k++] = i;
        dfs(_x, _y);
        s[--k] = '?';
        g[_x][_y] = false;
    }
}

int main() {
    scanf("%s", s);
    init();
    dfs(1, 1);
    printf("%d\n", ans);
    return 0;
}