Submission #2526975

---

Source Code Expand

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

typedef tuple<int,int,int> t;
int h,w;
int sx,sy,gx,gy;
char tw[505][505];

bool bfs() {
	int dx[] = {-1,0,1,0};
	int dy[] = {0,1,0,-1};
	bool brk[h][w][3];
	for (int y = 0;y < h;y++) {
		for (int x = 0;x < w;x++) {
			for (int i = 0;i < 3;i++) {
				brk[y][x][i] = false;
			}
		}
	}
	queue<t> que;
	que.push(t(sy,sx,0));
	while (que.size() > 0) {
		int y,x,b;
		tie(y,x,b) = que.front();
		que.pop();
		for (int i = 0;i < 4;i++) {
			int ny = y+dy[i];
			int nx = x+dx[i];
			if (0 <= ny && ny < h && 0 <= nx && nx < w) {
				if (brk[ny][nx][b]) continue;
				if (tw[ny][nx] == '#' && b == 2) continue;
				if (tw[ny][nx] == '#') {
					brk[ny][nx][b+1] = true;
					que.push(t(ny,nx,b+1));
				} else {
					brk[ny][nx][b] = true;
					que.push(t(ny,nx,b));
				}
			}
		}
	}
	return brk[gy][gx][0] || brk[gy][gx][1] || brk[gy][gx][2];
}

int main() {
	cin >> h >> w;
	//縦y
	for (int y = 0;y < h;y++) {
		for (int x = 0;x < w;x++) {
			cin >> tw[y][x];
			if (tw[y][x] == 's') {
				sy = y;
				sx = x;
			}
			if (tw[y][x] == 'g') {
				gy = y;
				gx = x;
			}
		}
	}
	if (bfs()) cout << "YES" << endl;
	else cout << "NO" << endl;
}

Submission Info

Judge Result