Submission #7558613

---

Source Code Expand

//
//  main.cpp
//  AT1350 深さ優先探索
//
//  Created by 马英粼 on 2019/9/16.
//  Copyright © 2019 马英粼. All rights reserved.
//

#include <iostream>
#include <string.h>
using namespace std;
char c[550][550];
int n, m, f_x, f_y, end_x, end_y;
int dx[4] = {0, 0, -1, 1}, dy[4] = { -1, 1, 0, 0}; //方向数组
bool flag = false, used[550][550];
void dfs(int a, int b) {
    if (flag == true)   return;
    if (a < 0 || a >= n || b < 0 || b >= m) return;
    if (a == end_x && b == end_y) {
        flag = true;
        return;
    }
    else if (c[a][b] == '#') {
        return;
    }
    for (int i = 0; i < 4; i++) {
        int x = a + dx[i];
        int y = b + dy[i];
        if (used[x][y]) {
            used[x][y] = false;
            dfs(x, y);
        }
    }
}
int main() {
    cin >> n >> m;
    memset(used, true, sizeof(used));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c[i][j];
            if (c[i][j] == 's') {
                f_x = i;
                f_y = j;
            }
            if (c[i][j] == 'g') {
                end_x = i;
                end_y = j;
            }
        }
    }
    used[f_x][f_y] = false;
    dfs(f_x, f_y);
    if (flag)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Submission Info

Judge Result