时间限制: 1 Sec 内存限制: 16 MB
提交: 595 解决: 207
[提交][状态][讨论版]题目描述
编一个程序，找出一条通过迷宫的路径。这里有兰色方块的区域表示走不通，将一只老鼠从入口处经过迷宫到出口处的一条通路打印出来。
老鼠寻路有8个方向,老鼠先探索1方向,若不通就改2方向,再不通再改3方向.........如图B.
输入
第1行2个整数 m,n 表示迷宫有m 行n列 （m ＜＝ 10,n ＜＝ 10） 下面m行,每行n个数据
输出
样例输入
7 6
0 0 1 0 1 0
0 1 1 1 1 1
1 0 0 1 0 0
0 0 1 0 0 1
1 1 0 0 1 0
0 0 1 0 0 1
0 1 0 0 1 0
样例输出
(1,1)-(1,2)-(2,1)-(3,2)-(3,3)-(4,4)-(4,5)-(5,6)-(6,5)-(7,6)
提示
注意：当不止一条路径时，老鼠选择探索方向的顺序直接影响着输出的第一条路径。本题规定了老鼠探索方向的顺序。
code
#include<iostream>
using namespace std;
const int N(15);
const int dx[]={ 1, 0,-1,-1,-1, 0, 1, 1};
const int dy[]={ 1, 1, 1, 0,-1,-1,-1, 0};
struct node{ int x,y;};
int m,n,map[N][N],t(0);
bool visited[N][N]={0},found(false);
node path[120];
void search(int x0,int y0)
{
if (found) return ;
if (x0==m&&y0==n)
{
cout<<'('<<1<<','<<1<<')';
for (int i=0;i<t;i++)
cout<<"-("<<path[i].x<<','<<path[i].y<<')';
cout<<endl;
found=true;
return;
}
int x1,y1;
node p;
for (int i=0;i<8;i++)
{
x1=x0+dx[i];
y1=y0+dy[i];
if (x1<1||x1>m||y1<1||y1>n) continue;
if (map[x1][y1]) continue;
map[x1][y1]=1;
p.x=x1; p.y=y1; path[t++]=p;
search(x1,y1);
map[x1][y1]=0;
--t;
}
}
int main()
{
cin>>m>>n;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
cin>>map[i][j];
if (!map[1][1])
{
map[1][1]=1;
search(1,1);
}
//cin.get();cin.get();
return 0;
}
posted on 2012-08-17 20:55
龙在江湖 阅读(835)
评论(0) 编辑 收藏 引用 所属分类:
搜索