問題概要

各マスが 0 または 1 であるような $H \times W$ の二次元グリッドが与えられる。

グリッド上の各マスを渡り歩いていく移動経路のうち、次の条件を満たすものを考える。

1 回の移動では、今いるマスから上下左右のマスに移動する
マスの値が 1 であるようなマスのみを通ることができる
一度通ったマスは二度以上通ることはできない

そのような経路のうち、通るマス数の最大値を求めよ。

制約

$1 \le H, W \le 90$
問題文の条件を満たすような経路の個数は $2 \times 10^{5}$ 以下

考えたこと

制約から「条件を満たす移動経路の個数は $2 \times 10^{5}$ 」とあるのですから、その移動経路を全探索しましょう！

このような複雑な全探索は不慣れだと難しいと感じるかもしれません。ここでは、次のような再帰関数を実装しましょう。

// seen：現在いるマスよりも前段階ですでに通って来たマスを表す。
// seen[i][j] = true であるようなマス (i, j) はもう使えない
// x, y：現在いるマスを表す
// 返り値：マス (x, y) を出発地としたときの、通るマス数の最大値
int dfs(int x, int y, vector<vector<bool>> &seen) {
    int res = 1;  // 1 はマス (x, y) を表す
    seen[x][y] = true;  // マス (x, y) はすでに通った扱いをする
    for (マス (x2, y2) : マス (x, y) から行けるマスの集合) {
        if (seen[x2][y2]) continue;  // すでに使ったマスは二度行けない
        res = max(res, dfs(x2, y2, seen) + 1);
    }
    seen[x][y] = false;  // マス (x, y) の探索を終えたので元に戻す
}

ここで、最後に seen[x][y] = false というように、元の状態に戻すのを忘れないようにしましょう。このような「後戻り」を用いた全探索をバックトラッキングと呼ぶことがあります。

バックトラッキングがピンと来ない方は、先に次の記事を読んでみてください。次の記事のコードの中に出てくる A.pop_back() といった処理と同じ考え方です。

drken1215.hatenablog.com

あとは、このような再帰関数 dfs の中身を実装しましょう。

コード

ここでは、再帰関数 dfs をラムダ式で実装しています。

#include <bits/stdc++.h>
using namespace std;

const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};

int main() {
    int H, W;
    cin >> H >> W;
    vector A(H, vector(W, 0));
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> A[i][j];

    auto dfs = [&](auto dfs, int x, int y, vector<vector<bool>> &seen) -> int {
        int res = 1;
        seen[x][y] = true;
        for (int d = 0; d < 4; d++) {
            int x2 = x + dx[d], y2 = y + dy[d];
            if (x2 < 0 || x2 >= H || y2 < 0 || y2 >= W) continue;
            if (seen[x2][y2]) continue;
            if (A[x2][y2] == 0) continue;
            res = max(res, dfs(dfs, x2, y2, seen) + 1);
        }
        seen[x][y] = false;
        return res;
    };

    int res = 0;
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        if (A[i][j] == 0) continue;
        vector seen(H, vector(W, false));
        res = max(res, dfs(dfs, i, j, seen));
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 予選 2009 D - 薄氷渡り (AOJ 0535) (2Q, 難易度 5)

問題概要

制約

考えたこと

コード