游客 注册 | 登录
中文 | En

2037 - Maze Problem

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

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

C语言解答

#include<stdio.h>
#include<string.h>
#define min(x,y) x>y?y:x
int a,b,c,d,p;
char map[103][103];
void dfs(int x,int y,int s)
{
    if(map[x][y]=='#')return ;
    if(x==c && y==d ){p=min(s,p);return ;}
    s++;
    map[x][y]='#';
    dfs(x+1,y,s);
    dfs(x,y+1,s);
    dfs(x-1,y,s);
    dfs(x,y-1,s);
    map[x][y]='-';
}
int main()
{
   // freopen("sousuo.txt","w",stdout);
    int T,n,m,i,j;
    scanf("%d",&T);
    while(T--)
    {
        memset(map,'#',sizeof(map));
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;++i)
        {
            getchar();
            for(j=1;j<=m;++j)
            {
                map[i][j]=getchar();
                if(map[i][j]=='S'){a=i;b=j;}
                if(map[i][j]=='E'){c=i;d=j;}
            }
        }
        p=11000;
        dfs(a,b,0);
        printf("%d\n",p);
    }
    return 0;
}

C++解答

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define min(x,y) x<y?x:y;
bool flag;
int x1,y1,x2,y2,a,b,m;
char map[103][103];
void dfs(int i,int j,int cnt)
{

    if(map[i][j]=='#') return ;
    if(i==x2&&j==y2)
    {
        m=min(cnt,m);
        flag= false;
        return ;
    }
    if(i>=1&&i<=a&&j>=1&&j<=b&&map[i][j]!='#')
    {
        cnt++;
        map[i][j]='#';
        dfs(i,j-1,cnt);
        dfs(i-1,j,cnt);
        dfs(i,j+1,cnt);
        dfs(i+1,j,cnt);
        map[i][j]='-';
    }
}
int main()
{
    int T,i,j;
    cin>>T;
    while(T--)
    {
        m = 100000;flag = true;
        scanf("%d%d",&a,&b);
        for(i = 1 ; i <= a; i++)
        {
            for(j = 1 ; j <= b; j++)
            {
                cin>>map[i][j];
                if(map[i][j]=='S')
                    x1=i,y1=j;
                if(map[i][j]=='E')
                {
                    x2=i,y2=j;
                }
            }
        }
        dfs(x1,y1,0);
        if(!flag)
        printf("%d\n",m);
        else
        printf("-1\n");
    }
    return 0;
}
请先登陆