Submission #2524233

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int h, w, start_h, start_w, end_h, end_w;
char M[502][502];
bool check[502][502];
bool flag;

void f(int i, int j, int cnt) {
    
    if (i > h || j > w) return;
    if (i <= 0 || j <= 0) return;
    
    if (check[i][j])
        return;
    
    //cout << i << " " << j << " : " << cnt << "\n";
    check[i][j] = true;
    if (M[i][j] == '#') {
        cnt++;
        if (cnt > 2) return;
    }
    
    if (i == end_h && j == end_w) {
        flag = true;
        return;
    }
    f(i, j + 1, cnt); // right
    f(i + 1, j, cnt); // down
    f(i, j - 1, cnt); // left
    f(i - 1, j, cnt); // up
    
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> h >> w;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> M[i][j];
            if (M[i][j] == 's') {
                start_h = i;
                start_w = j;
            }
            if (M[i][j] == 'g') {
                end_h = i;
                end_w = j;
            }
            
        }
    }
    
    f(start_h, start_w, 0);
    if (flag)
        cout << "YES\n";
    else
        cout << "NO\n";
}

Submission Info

Judge Result