Submission #7973926

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
 
void fill_island(vector<vector<char>> &map, vector<vector<bool>> &checked, int x, int y) {
  if (y < 0 || x < 0 || x >= map.size() || y >= map.at(0).size()) return;
  if (map.at(x).at(y) == '#') return;
  if (checked.at(x).at(y) == true) return;
 
  checked.at(x).at(y) = true;
  fill_island(map, checked, x    , y - 1);  // 上に探索を続ける
  fill_island(map, checked, x + 1, y    );  // 右に探索を続ける
  fill_island(map, checked, x    , y + 1);  // 下に探索を続ける
  fill_island(map, checked, x - 1, y    );  // 左に探索を続ける
}

bool check_connected(vector<vector<char>> &map) {
  vector<vector<bool>> checked(10, vector<bool>(10, false));
 
  // スタート地点を探す
  int x, y;
  for (int i = 0; i < map.size(); i++) {
    for (int j = 0; j < map.at(0).size(); j++) {
      if (map.at(i).at(j) == 's') {
        x = i;
        y = j;
        break;
      }
    }
  }
  
  // スタート地点から上下左右に限界まで探して可能な限り通過したmapにtrueをつける
  fill_island(map, checked, x, y);

  // ゴールの座標にtrueが付いているかをcheckする
  bool ok = true;
  for (int i = 0; i < map.size(); i++) {
    for (int j = 0; j < map.at(0).size(); j++) {
      if (map.at(i).at(j) == 'g') {
        if (!checked.at(i).at(j)) {
          ok = false;
        }
      }
    }
  }
 
  return ok;
}

int main() {
    int H, W;
    cin >> H >> W;

    vector<vector<char>> map(H, vector<char>(W));
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W ; j++){
            cin >> map.at(i).at(j);
        }
    }
    
    if(check_connected(map)){
        cout << "YES" << endl;
        return 0;
    }

    cout << "NO" << endl;
}

Submission Info

Judge Result