Submission #1023134

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

#define INF 1e9

int h, w;
vv<char> city;
deque<deque<bool> > reached;

int dh[4] = {1, 0, -1,  0};
int dw[4] = {0, 1,  0, -1};
int sh, sw, gh, gw;

vector<pii> will_destruct;

void dfs(int ih_, int iw_) {
  reached.assign(h+2, deque<bool>(w+2, false));

  deque<pii> st;
  st.push_back(mp(ih_, iw_));
  reached[ih_][iw_] = true;
  while (!st.empty()) {
    int ih = st.front().first;
    int iw = st.front().second;
    st.pop_front();
    reached[ih][iw] = true;
    if (ih == gh && iw == gw) {
      return;
    }

    rep (i, 4) {
      int jh = ih + dh[i];
      int jw = iw + dw[i];
      if (city[jh][jw] == '@' || reached[jh][jw]) {
        continue;
      }
      reached[jh][jw] = true;
      if (city[jh][jw] == '#') {
        will_destruct.push_back(mp(jh, jw));
        continue;
      }
      st.push_back(mp(jh, jw));
    }
  }

  return;
}

int main() {
  scanf("%d %d", &h, &w);
  city.assign(h+2, vector<char>(w+2, '@')); // @ : Guard
  FOR (i, 1, h+1) {
    FOR (j, 1, w+1) {
      scanf(" %c", &city[i][j]);
      switch (city[i][j]) {
      case 's':
        sh = i;
        sw = j;
        break;
      case 'g':
        gh = i;
        gw = j;
        break;
      }
    }
  }

  // cost == 1 を列挙、取り壊す
  will_destruct.reserve(h * w);
  dfs(sh, sw);
  if (reached[gh][gw]) {
    printf("YES\n");
    return 0;
  }
  for (pii pi : will_destruct) {
    city[pi.first][pi.second] = '.';
  }

  // cost == 2 を列挙、取り壊す
  will_destruct.clear();
  will_destruct.reserve(h * w);
  dfs(sh, sw);
  if (reached[gh][gw]) {
    printf("YES\n");
    return 0;
  }
  for (pii pi : will_destruct) {
    city[pi.first][pi.second] = '.';
  }

  dfs(sh, sw);

  if (reached[gh][gw]) {
    printf("YES\n");
  } else {
    printf("NO\n");
  }

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &h, &w);
                         ^
./Main.cpp:91:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
       scanf(" %c", &city[i][j]);
                                ^

Judge Result