読者です 読者をやめる 読者になる 読者になる

AGC007 A - Shik and Stone

問題

グリッドを左上から右下まで移動した。移動したマスは'#'であり、そうでないマスは'.'である。何度も同じ場所を行き来することもある。右または下にだけ移動した可能性のある場合は"Possible"、そうでない場合は"Impossible"を出力せよ。

解答

必ず左上から右下まで移動したので、'#'のマスの数がH+W-1個分存在するか調べるだけで良い。 また、左上から右下まで、右または下の移動で到達できるかシミュレートしても良い。ただし、その場合は次のようなケースに注意する。

3 3
#..
#.#
###

このケースでは、右下に到達した後に上に移動している。右下に到達した後に左に移動するようなケースも同様に注意する。

int main() {
 
  int H, W; cin >> H >> W;
  int sum = 0;
  rep(i, H) {
    string A; cin >> A;
    sum += count(A.begin(), A.end(), '#');
  }
 
  cout << (sum == H + W - 1 ? "P":"Imp") << "ossible\n";
  
  return 0;
}