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

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注