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

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

AtCoder AGC 007 A - Shik and Stone (茶色, 200 点)

AtCoder AtCoder200点 AGC-A 二次元グリッド 最適化の考察：最適解の形を考える 競技数学色強め 茶色diff 駒(コマ)や石やコインを扱う問題

高校の頃とかに「グリッドの左上から右下まで行く最短路が何通りあるか」みたいな問題に親しんでいれば、自然に思えるかもしれない

問題へのリンク

問題概要

H × W のグリッドがあって、最初は駒は左上隅に置かれていた。

駒が上下左右に動きながら右下隅まで移動した。駒は同じマスを何度も通った可能性もある。

駒が一度でも通った場所が黒く塗られている。黒く塗られた盤面が与えられて、駒が「右」と「下」にしか動いていないかどうかを判定せよ。

制約

  • 2 \le H, W \le 8
  • 与えられた黒塗り盤面を実現するような駒の動きが存在することは保証される。

考えたこと

以下のことが同値であることはよく知られている

  • 駒は左上から右下へと最短経路を移動した
  • 駒は「右」か「下」にしか移動していない

これは高校時代に下図のような道順問題 (S から T へ最短でいくのは何通りか) みたいな問題を解いたことがあれば、納得のできる話だと思う。

つまり上図で言えば、結局最短路とは

  • 右に 4 回
  • 下に 3 回

移動するということに他ならないので、右移動 4 個と、下移動 3 個とを並べる場合の数を求めればいいので C(7, 3) 通りになるという論法だ。

これを思い出せば、本問題において

  • 駒が「右」と「下」にしか移動していない

というのはつまり

  • 駒が最短で右下へと移動している

ということなので、黒く塗られたマスの個数がちょうど H + W - 1 マスであることが予め確定するのだ。よって単に黒マスの個数を数え上げて、それが H + W - 1 かどうかを判定すればよい。

注意点として、もし与えられた盤面が「駒が左上から右下への移動として適切とは限らない」のであればこれだけでは不足なのだが、今回はそれが確定しているので問題ない。

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

int main() {
    int H, W; cin >> H >> W;
    int count = 0;
    for (int i = 0; i < H; ++i) {
        string S; cin >> S;
        for (auto c : S) if (c == '#') ++count;
    }
    if (count == H + W - 1) cout << "Possible" << endl;
    else cout << "Impossible" << endl;
}