欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

走迷宫(深搜做法+)

程序员文章站 2022-03-03 11:13:17
...

走迷宫

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 85  Solved: 77
[Submit][Status][Web Board]

Description

X身在一个M*N大小的迷宫中,迷宫中的障碍物是不能通行的。迷宫中用S代表X,用E代表出口,#代表障碍物,*代表可以通行的道路。X只可以向上、下、左、右四个方向行走,并且每一步只能走一个单位的长度。现给定M,N以及迷宫的样子,求解X走到出口的过程中最少需要改变行走方向几次?如果X无法到达出口就输出 -1,否则输出需要的最小改变方向次数,X会尽量走改变方向较少的路线,只要相邻两次行走方向不一样就算改变方向一次。 (1<=M,N<=100)

Input

有多组输入数据,每组第一行输入两个正整数M和N,
接下来输入M*N的迷宫,迷宫元素只包含S、E、*、#四种字符。
输入以文件为结束(EOF)。

Output

对于每组数据,如果X能从S能到达出口E,输出最少改变方向次数,否则输出-1,每组输出占一行。

Sample Input

5 5
S****
####*
*****
*####
****E

Sample Output

4

HINT

因为障碍物(#)不能通行,所以S只能通过*到达E,最少需要转弯4次

//比较简单的水题,深搜广搜都能解,先发深搜解法,重点就是z,sum,z是我方向数组的下标,如果z和i不一样说明方向变了,转了一次弯,就+1,否则就不变,用递归回溯模拟走的方向

# include <iostream>
# include <cstring>
using namespace std;

char str[105][105];

int sx, sy, px, py;
int n, m;
int f[105][105];
int flag = 0;
int dis[][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void dfs(int x, int y,int z,int sum)
{
    //cout << "x = " << x << " y = " << y << endl;
     //cout << " z = " << z << " sum = " << sum << endl;
    if(x == px && y == py)
    {
        flag = 1;
        cout << sum <<endl;
        return ;
    }
    for(int i = 0; i < 4; i++)
    {

        int tx = x + dis[i][0];
        int ty = y + dis[i][1];

        //cout << "tx = " << tx << " ty =" << ty <<  " ch = "<<str[tx][ty]<< endl;
        if(tx < 0 || tx >=n || ty < 0 || ty >= m || str[tx][ty] != '*')
        {
            continue;
        }
        if(f[tx][ty]  == 0)
        {
                f[tx][ty] = 1;
            if(z == -1)
            {
                dfs(tx, ty,i,sum);
            }
            else
            {

                 if(i != z)
                 {
                    //f[tx][ty] = 1;
                    dfs(tx,ty,i,sum +1);
                    //f[tx][ty] = 0;
                 }
                 else
                    dfs(tx,ty,i,sum);
            }
                f[tx][ty] = 0;
            //dfs(tx, ty);
        }
    }
    return ;
}

int main(int argc, char *argv[])
{
    while(cin >> n >> m)
    {
        flag = 0;
        memset(str, 0, sizeof(str));
        for(int i = 0; i < n; i++)
        {
            cin >> str[i];
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(str[i][j] == 'S')
                {
                    sx = i;
                    sy = j;
                    str[i][j] = '*';
                }
                if(str[i][j] == 'E')
                {
                    px = i;
                    py = j;
                    str[i][j] = '*';
                }
            }
        }
        dfs(sx, sy,-1,0);
    /*    if(flag)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
        */
    }
    return 0;
}