走迷宫(深搜做法+)
程序员文章站
2022-03-03 11:13:17
...
走迷宫
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 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)。
接下来输入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;
}
下一篇: 深搜-迷宫