Submission #5013223

---

Source Code Expand

/*********************************************************************

* 题目：洛谷-AT1350-深度优先搜索 
* 作者：小韦同学
* 邮箱：weichangying_wcy@163.com

*********************************************************************/

#include <bits/stdc++.h>

using namespace std;

const int N = 510;
string maze[N];
bool vis[N][N];
int n, m;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

bool in(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < m;
}

bool dfs(int x, int y) {
	//  若到达终点，则返回true 
	if (maze[x][y] == 'g') return true;
	vis[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int tx = x + dir[i][0];
		int ty = y + dir[i][1];
		//  (tx, ty)这个点没有越界，不是墙，并且还没有被访问过 
		if (in(tx, ty) && maze[tx][ty] != '#' && !vis[tx][ty]) {
			if (dfs(tx, ty)) return true;
		}
	}
	//  回溯 
	//vis[x][y] = false;
	return false;
}

int main() {

	cin >> n >> m;
	// 输入地图 
	for (int i = 0; i < n; i++) {
		cin >> maze[i];
	}
	int x, y;  //  代表起点坐标
	//  找起点坐标 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (maze[i][j] == 's') {
				x = i;
				y = j;
			}
		}
	}
	if (dfs(x, y)) cout << "Yes";
	else cout << "No";
	
	return 0;
}

Submission Info

Judge Result