Submission #2997337

---

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];
int d[500][500];//-1なら未到達　0なら到達　1なら壁を一回壊して到達　2なら二回壊して到達
int d2[500][500];//
int sx, sy, gx, gy;
/*
2 2
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 (d[nx][ny] >= get<2>(t)+1) {
							d[nx][ny] = get<2>(t) + 1;
							que.push(make_tuple(nx, ny, get<2>(t) + 1));
							
						}
					}
					else {
						if (d[nx][ny] >= get<2>(t)) {
							que.push(make_tuple(nx, ny, get<2>(t)));
							d[nx][ny] = get<2>(t);
						}
					}
				}
				else if (get<2>(t) == 2) {
					if (field[nx][ny] != '#') {
						if (d[nx][ny] >= get<2>(t)) {
							que.push(make_tuple(nx, ny, get<2>(t)));
							d[nx][ny] = get<2>(t);
						}
					}
				}
			}
		}
	}

}
int main() {
	memset(d, -1, sizeof(d));
	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