Submission #421077

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>
#include <math.h>
using namespace std;

vector<pair<int, int>> list;
int H, W;
vector<char> C;

bool isPush(int i, int j)
{
	if (C[i*W + j] == 'g')
	{
		return true;
	}
	else if (C[i*W + j] != '#')
	{
		C[i*W + j] = '#';
		return true;
	}
	return false;
}

void prepare(int Si, int Sj)
{
	//left
	if (Sj - 1 >= 0)
	{
		if (isPush(Si, Sj - 1))
		{
			pair<int, int> cij(Si, Sj - 1);
			list.push_back(cij);
		}
	}
	//right
	if (Sj + 1 < W)
	{
		if (isPush(Si, Sj + 1))
		{
			pair<int, int> cij(Si, Sj + 1);
			list.push_back(cij);
		}
	}
	//top
	if (Si - 1 >= 0)
	{
		if (isPush((Si-1), Sj))
		{
			pair<int, int> cij((Si - 1), Sj);
			list.push_back(cij);
		}
	}
	//down
	if (Si + 1 < H)
	{
		if (isPush((Si + 1), Sj))
		{
			pair<int, int> cij((Si + 1), Sj);
			list.push_back(cij);
		}
	}

}

int main()
{
	cin >> H >> W;
	int Si, Sj;
	int Gi, Gj;

	for (size_t i = 0; i < H; ++i)
	{
			string str;
			cin >> str;
			for (size_t k = 0; k < str.length(); ++k)
			{
				char cij = str[k];
				C.push_back(cij);
				if (cij == 's')
				{
					Si = i; Sj = k;
				}
				else if (cij == 'g')
				{
					Gi = i; Gj = k;
				}
			}
	}

	prepare(Si, Sj);

	while (1)
	{
		if (list.size() == 0)
			break;

		pair<int, int> target = list.back();
		list.pop_back();

		if (C[W*target.first + target.second]=='g')
		{
			cout << "Yes" << endl;
			return 0;
		}

		prepare(target.first, target.second);
	}
	
	cout << "No" << endl;
	return 0;
}

Submission Info

Judge Result