Maze Problem

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;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。