Submission #2983581

---

Source Code Expand

#include<bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;
using ll = long long;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int H, W;
char field[500][500];
bool d[500][500];
int d2[500][500];//s
int sx, sy, gx, gy;
/*
10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g##.#.#.#.
###.#.#.#.
###.#.#.#.
#.....#...
*/
void bfs() {
	queue<tuple<int, int, int>>que;
	que.push(make_tuple(sx,sy,0));
	d[sx][sy] = true;
	while (!que.empty()) {
		tuple<int, int, int>t = que.front();
		que.pop();
		if (get<0>(t) == gx&&get<1>(t)==gy&&get<2>(t)<=2) {
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nx = get<0>(t) + dx[i];
			int ny = get<1>(t) + dy[i];
			if (0 <= nx && nx < H && 0 <= ny && ny < W) {
				if (get<2>(t) <= 1) {
					if (field[nx][ny] == '#') {
						if (d2[nx][ny] >= d2[get<0>(t)][get<1>(t)] + 1) {
							que.push(make_tuple(nx, ny, get<2>(t) + 1));
							d[nx][ny] = true;
							d2[nx][ny] = d2[get<0>(t)][get<1>(t)] + 1;
						}
					}
					else {
						que.push(make_tuple(nx, ny, get<2>(t) ));
						d[nx][ny] = true;
						d2[nx][ny] = d2[get<0>(t)][get<1>(t)];
					}
				}
				else if (get<2>(t) == 2) {
					if (field[nx][ny] != '#') {
						que.push(make_tuple(nx, ny, get<2>(t) ));
						d[nx][ny] = true;
						d2[nx][ny] = d2[get<0>(t)][get<1>(t)];
					}
				}
			}
		}
	}
	
}
int main() {
	for (int i = 0; i < 500; i++) {
		for (int j = 0; j < 500; j++) {
			field[i][j] = '#';
		}
	}
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> field[i][j];
			if (field[i][j] == 's') {
				sx = i;
				sy = j;
			}
			else if (field[i][j] == 'g') {
				gx = i;
				gy = j;
			}
		}
	}
	bfs();
	if (d[gx][gy]) {
		cout<<"YES"<<endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}

Submission Info

Judge Result