萌新过不了样例
查看原帖
萌新过不了样例
757409
Flying_Eagle楼主2023/3/6 20:55
#include <bits/stdc++.h>
using namespace std;
int n, m;
char mp[1005][1005];
bool vis[1005][1005];
int sx, sy;

const int dx[] = {1, 0, -1, 0};

const int dy[] = {0, 1, 0, -1};

struct node {
	int x, y, dep;
};

bool good(int x, int y) {
	return (x <= n && x >= 1 && y <= m && y >= 1) && !vis[x][y] && mp[x][y] != '#';
}

void bfs() {
	queue<node> q;
	q.push({sx, sy, 0});
	vis[sx][sy] = true;
	while (!q.empty()) {
		node t = q.front();
		q.pop();
		if (t.x == n-1 && t.y == m-1) {
			cout << "Yes" << endl;
			return ;
		}
		for (int i = 0; i < 4; i++) {
			int xnew = t.x + dx[i], ynew = t.y + dy[i];
			if (good(xnew, ynew)) {
				q.push({xnew, ynew, t.dep + 1});
				vis[xnew][ynew] = true;
			}
		}
	}
	cout << "No" << endl;
}

int main() {
	
	while (cin >> n >> m) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> mp[i][j];
				if (mp[i][j] == 'S') {
					sx = i, sy = j;
				}
			}
		}
		memset(vis, false, sizeof(vis));
		bfs();
	}
	return 0;
}
2023/3/6 20:55
加载中...