Maze Problem
时间: 1ms 内存:128M
描述:
Given a maze, find a shortest path from start to goal.
输入:
Input consists serveral test cases.
First line of the input contains number of test case T.
For each test case the first line contains two integers N , M ( 1 <= N, M <= 100 ).
Each of the following N lines contain M characters. Each character means a cell of the map.
Here is the definition for chracter.
Constraint:
- For a character in the map:
- 'S' : start cell
- 'E' : goal cell
- '-' : empty cell
- '#' : obstacle cell
- no two start cell exists.
- no two goal cell exists.
输出:
For each test case print one line containing shortest path. If there exists no path from start to goal, print -1.
示例输入:
1
5 5
S-###
-----
##---
E#---
---##
示例输出:
9
提示:
参考答案(内存最优[748]):
#include<stdio.h>
void main()
{
int a;char b;
while(scanf("%d",&a)!=EOF){
b=a;
printf("%c",b);
}
}
参考答案(时间最优[0]):
#include <iostream>
#include <deque>
#define MAX 101
using namespace std;
char s[MAX][MAX];
int x[]={1,-1,0,0};
int y[]={0,0,-1,1};
struct ss
{
int x,y;
int time;
};
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
deque<ss> q;
int i,j;
int sx,sy;
for(i=0;i<n;++i)
{
for(j=0;j<m;++j)
{
cin>>s[i][j];
if(s[i][j]=='S')
{
sx=i,sy=j;
s[i][j]='#';
}
}
}
ss present;
present.x=sx;
present.y=sy;
present.time=0;
while(s[present.x][present.y]!='E')
{
ss w;
w.time=present.time+1;
for(i=0;i<4;i++)
{
w.x=present.x+x[i];
w.y=present.y+y[i];
if(w.x<0||w.y<0||w.x>=n||w.y>=m)continue;
if(s[w.x][w.y]=='#')continue;
if(s[w.x][w.y]!='E')
s[w.x][w.y]='#';
q.push_back(w);
}
if(q.empty())break;
present=q.front();
q.pop_front();
}
if(q.empty()&&s[present.x][present.y]!='E')cout<<-1<<endl;
else cout<<present.time<<endl;
}
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。