Submission #421258

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<queue>
using namespace std;

typedef pair<int, int> pi;
pair <int, int>p;
pair <int, int> po;
int n, m;
int xx, yy;
char ma[1001][1001];
int te[1001][1001];
int xw[4] = { 1, 0, -1, 0 };
int yw[4] = { 0, 1, 0, -1 };
int op = 100000;
int main()
{

	queue<pi> q;
	cin >> n >> m;
	for (int i = 0; i < n; i++){
		cin >> ma[i];
	}
	for (int i = 0; i < 1001; i++){
		for (int i2 = 0; i2 < 1001; i2++){
			te[i][i2] = op;
		}
	}
		for (int i = 0; i <n; i++){
		for (int i2 = 0; i2 <m; i2++){
			if (ma[i][i2] == 's'){
				p.first = i2;
				p.second = i;
			}
			else if (ma[i][i2] == 'g'){
				xx = i;
				yy = i2;
			}
		}
	}
	int count;
	count = 0;
	q.push(p);

	te[p.first][p.second] = 0;
	bool flag = false;
	while (!q.empty()){
		p = q.front();
		po = p;
		q.pop();
		for (int i = 0; i < 4; i++){
			int x = p.first + xw[i];
			int y = p.second + yw[i];
			if (0 <= x && x < n && 0 <= y && y < m &&ma[x][y] == 'g'){
				te[x][y] = te[p.first][p.second] + 1;
				flag = true;
				break;
			}
			if (0 <= x && x<n && 0 <= y && y<m && ma[x][y] == '.' && te[x][y] == op){
					po.first = x;
					po.second = y;
					q.push(po);
					po = p;
					te[x][y] = te[p.first][p.second] + 1;
			}
		}
	}
	if (te[xx][yy]!=op){cout << "Yes" << endl;}
	else{ cout << "No" << endl; }
	
}

Submission Info

Judge Result