百练/2018ビッグデータ研究センターサマーキャンプ上机试験C:迷宫から脱出

テーマの出所:http://bailian.openjudge.cn/dsj2018xly/C
C:迷宮から逃げる
合計時間制限: 1000ms    メモリの制限: 65536kB
説明
あなたは地下の迷宮の中で宝を見つけましたが、迷宮機関をトリガーし、迷宮がT分後に崩壊することになります.そのため、T分以内に迷宮を脱出する必要があります.迷宮から脱出できるかどうか知りたいです.迷宮は辺長mの正方形で、「S」はあなたの位置を表し、「E」は迷宮出口を表し、「.」は自由に歩くことができるエリアで、「#」は通り抜けられない壁で、毎回1分かけてエリア間を移動することができます(上下左右4方向).
入力
入力には複数の配列が含まれ、最初の行は整数K(1<=K<=10)であり、K群データがあることを示す.次に各配列は整数m(2<=m<=10)と整数Tを含み、mは正方形迷路の辺長を表し、Tは崩壊時間を表す.その後、m*mの文字行列であり、文字「S」、「E」、「.」、「#」を含む.
しゅつりょく
各グループのデータは1行ずつ出力され、「YES」または「NO」が出力され、崩壊前に脱出できるか(すなわち、移動回数がTを超えないか)を示す.
サンプル入力

2
4 7 
S...
###.
.#E.
..#.     
3 4
S..
..#
.#E

サンプル出力

YES
NO

--------------------------------------------------------------
構想
権限を持たない最短ルートを広く捜索する
-----------------------------------------------------
コード#コード# 

#include
#include
#include
using namespace std;

struct node {
	int x,y;
	int tcnt;

	node(void) {}
	node(int xx, int yy, int tt): x(xx), y(yy), tcnt(tt){}
};

int m,t;
char mat[12][12] = {};

int bfs(int x0, int y0, int x1, int y1)
{
	if (x0==x1 && y0==y1)
	{
		return 0;
	}
	node nd(x0, y0, 0);
	int x,y;
	queue q;
	q.push(nd);
	while (!q.empty())
	{
		nd = q.front();
		q.pop();
		x = nd.x;
		y = nd.y;
		if (x0)
		{
			if (mat[x-1][y]=='E')
			{
				return nd.tcnt+1;
			}
			else if (mat[x-1][y]=='.')
			{
				q.push(node(x-1,y,nd.tcnt+1));
				mat[x-1][y] = '*';
			}
		}
		if (y0)
		{
			if (mat[x][y-1]=='E')
			{
				return nd.tcnt+1;
			}
			else if (mat[x][y-1]=='.')
			{
				q.push(node(x,y-1,nd.tcnt+1));
				mat[x][y-1] = '*';
			}
		}
	}
	return -1;
}


int main()
{
#ifndef ONLINE_JUDGE
	ifstream fin ("C.txt");
	int k,i,j,x0,y0,x1,y1,ans;
	fin >> k;
	while (k--)
	{
		fin >> m >> t;
		for (i=0; i> mat[i][j];
				if (mat[i][j]=='S')
				{
					x0 = i;
					y0 = j;
				}
				else if (mat[i][j]=='E')
				{
					x1 = i;
					y1 = j;
				}
			}
		}
		ans = bfs(x0,y0,x1,y1);
		if (ans <= t && ans >= 0)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
	fin.close();
#endif
#ifdef ONLINE_JUDGE
	int k,i,j,x0,y0,x1,y1,ans;
	cin >> k;
	while (k--)
	{
		cin >> m >> t;
		for (i=0; i> mat[i][j];
				if (mat[i][j]=='S')
				{
					x0 = i;
					y0 = j;
				}
				else if (mat[i][j]=='E')
				{
					x1 = i;
					y1 = j;
				}
			}
		}
		ans = bfs(x0,y0,x1,y1);
		if (ans <= t && ans >= 0)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
#endif
}