[TJOI2007] 跳棋(Chinese Checkers) 题解

思路分析

从起点 $(x, y)$ 出发做回溯 DFS，初始标记 vis[x][y] = true。在当前位置 $(r, c)$ 枚举上下左右 $4$ 个方向：沿该方向一步步扫描 $k = 1, 2, \dots$，若遇到 1 则继续向前；一旦遇到第一个 0 格 $(nr, nc)$，若 $k \ge 2$（即中间至少越过了 $1$ 个 1 格）且 !vis[nr][nc]，则可跳至 $(nr, nc)$ 并累加距离 $k$，回溯后取消标记；注意无论该 0 格是否访问过，都不能越过 0 格继续往后跳，必须立刻 break 停止该方向的扫描。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

int n, sx, sy;
int g[105][105];
bool vis[105][105];
int ans = 0;
const int DR[4] = {-1, 1, 0, 0};
const int DC[4] = {0, 0, -1, 1};

void dfs(int r, int c, int dist)
{
    if (dist > ans) ans = dist;
    for (int d = 0; d < 4; ++d)
    {
        int k = 1;
        while (true)
        {
            int nr = r + k * DR[d];
            int nc = c + k * DC[d];
            if (nr < 1 || nr > n || nc < 1 || nc > n) break;
            if (g[nr][nc] == 1)
            {
                ++k;
                continue;
            }
            if (k >= 2 && !vis[nr][nc])
            {
                vis[nr][nc] = true;
                dfs(nr, nc, dist + k);
                vis[nr][nc] = false;
            }
            break;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> sx >> sy)) return 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> g[i][j];
    vis[sx][sy] = true;
    dfs(sx, sy, 0);
    cout << ans << "\n";
    return 0;
}