Submission #420860

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

const int start = 1;
const int goal = 2;
const int pavement = 0;
const int wall = 9;
const int used = 3;

typedef struct {
	int y;
	int x;
} position;

inline position operator+(position p1, position p2) {
	position p_return={
		p1.y + p2.y,
		p1.x + p2.x
	};
	return p_return;
}
int main() {
	position s;
	vector<position> lst;
	int H, W;
	cin >> H >> W;
	int board[H][W];
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			char c;
			cin >> c;
			switch (c) {
				case 's': {
					board[i][j] = start;
					s = {i, j};
					lst.push_back(s);
					break;
				}
				case 'g': { board[i][j] = goal;		 	break; }
				case '.': { board[i][j] = pavement; break; }
				case '#': { board[i][j] = wall; 		break; }
			}
		}
	}
	while (true) {
		std::cerr << std::endl;
		if (lst.size() == 0) {
			std::cout << "No" << std::endl;
			goto END;
		}
		s = lst.back(), lst.pop_back();
		board[s.y][s.x] = used;
		const position ds[] { {-1, 0}, {0, 1}, {0, -1}, {1, 0}};
		for (position d : ds) {
			position t = s + d;
			if (!(t.y < 0 || H <= t.y ||
					t.x < 0 || W <= t.x)) {
				if (board[t.y][t.x] == goal) {
					std::cout << "Yes" << std::endl;
					goto END;
				}
				if (board[t.y][t.x] == pavement) {
					lst.push_back(t);
				}
			}
		}

	}
END:

	return 0;
}

Submission Info

Judge Result