当前位置：网站首页>1256: bouquet for algenon

1256: bouquet for algenon

2022-04-23 13:59:00 【A program for beating the keyboard】

1256： A bouquet for Algernon

The time limit : 1000 ms Memory limit : 65536 KB
Submission number : 9651 Passing number : 4023

【 Title Description 】

Algernon is a clever and lazy white mouse , It's best at walking all kinds of mazes . Today it will challenge a very big maze , To encourage algenon to reach the finish line as soon as possible , At the end, there was a piece of algenon's favorite cheese . Now researchers want to know , If algenon is smart enough , How long does it take at least to eat cheese .

The maze uses a R×C Character matrix to represent . character S Indicates where algenon is , character E Indicates the location of the cheese , character # Wall , character . To show that one can pass through . Algenon is 1 Within a unit time, you can go from the current position to any position in its up, down, left and right directions , But you can't go out of the map boundary .

【 Input 】

The first line is a positive integer T（1 ≤ T ≤ 10）, Means that there are T Group data .

The first row of each set of data contains two positive integers separated by spaces R and C（2 ≤ R, C ≤ 200）, Indicates that the map is a R×C Matrix .

Next R Line describes the specific content of the map , Each line contains C Characters . The meaning of the characters is described in the Title Description . There must be and only one S and E.

【 Output 】

For each set of data , Output the least unit time that algenon eats cheese . If algenon can't get cheese , The output “oop!”（ Only output the contents in quotation marks , Do not output quotation marks ）. The output result of each group of data occupies one line .

【 sample input 】

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

【 sample output 】

5
1
oop!

【AC Code 】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
const int INF=0x3f3f3f3f;
inline int read()
{
	char ch=getchar();
	int n=0,m=1;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')m=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
	return n*m;
}
void write(int n)
{
	if(n>9)write(n/10);
	putchar(n%10+'0');
}
int t,r,c,sx,sy,dir[4][2]={
   {-1,0},{1,0},{0,-1},{0,1}};
char m[N][N];
bool vis[N][N];
struct point
{
	int px,py,pt;
};
queue<point> q;
void bfs(int tx,int ty,int tt)
{
	q.push((point){tx,ty,tt});
	vis[tx][ty]=1;
	while(!q.empty())
	{
		point p=q.front();
		q.pop();
		if(m[p.px][p.py]=='E')
		{
			cout<<p.pt<<"\n";
			return;
		}
		for(int i=0;i<4;i++)
		{
			int nx=p.px+dir[i][0],ny=p.py+dir[i][1];
			if(nx>0&&nx<=r&&ny>0&&ny<=c&&m[nx][ny]!='#'&&vis[nx][ny]==0)
			{
				q.push((point){nx,ny,p.pt+1});
				vis[nx][ny]=1;
			}
		}
	}
	cout<<"oop!\n";
}
int main(int argc,char **argv)
{
	t=read();
	while(t--)
	{
		r=read(),c=read();
		memset(vis,0,sizeof vis);
		memset(m,'\0',sizeof m);
		while(!q.empty())q.pop();
		for(int i=1;i<=r;i++)
			for(int j=1;j<=c;j++)
			{
				cin>>m[i][j];
				if(m[i][j]=='S')sx=i,sy=j;
			}
		bfs(sx,sy,0);
	}
	return 0;
}