はまやんはまやんはまやん

hamayanhamayan's blog

Right Down Path [CSAcademy #70 B]

https://csacademy.com/contest/round-70/task/right-down-path/

縦N,横Mのバイナリ行列がある。
ここから

  • ある1つのセルを決める
  • そこから最低1セル右に進む
  • そこから更に最低1セル下に進む

のように移動する。
移動できるのは1のマスだけであるとき、作れるパスの最大長は?

解法

2つDPを作って答える。
dwn[y][x] := 頂点(x,y)から下に移動できる最大長
lft[y][x] := 頂点(x,y)から左に移動できる最大長
これを事前に計算しておく。
 
パスは7の様な形になるので曲がる座標を全探索して答えを導こう。
曲がる座標を(x,y)とすると、

  • 2 ≦ dwn[y][x](最低1回右に移動可能)
  • 2 ≦ lft[y][x](最低1回下に移動可能)
  • A[y][x] == 1(そこで曲がれる)

の条件をみたす時に有効なパスを作れる。
この時の最大長はdwn[y][x] + lft[y][x] - 1となるので、この最大値を答えればよい。

int H, W, A[303][303];
int dwn[303][303], lft[303][303];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];

    rrep(y, H - 1, 0) rep(x, 0, W) if (A[y][x] == 1) {
        chmax(dwn[y][x], 1);
        chmax(lft[y][x], 1);
        if (y < H - 1) chmax(dwn[y][x], dwn[y + 1][x] + 1);
        if (x) chmax(lft[y][x], lft[y][x - 1] + 1);
    }

    int ans = 0;
    rep(y, 0, H) rep(x, 0, W) if(A[y][x] and 2 <= dwn[y][x] and 2 <= lft[y][x]) chmax(ans, dwn[y][x] + lft[y][x] - 1);
    cout << ans << endl;
}