冬天¤不回来
海风轻轻吹过我的脸庞 阳光温柔的洒在我身上 海鸥自由的飞在天空中像 快乐的徘徊在游乐场 白云在偷看彩虹的模样 海洋总为那船长指方向 海浪抚摸著沙滩的衣裳 我也每天都为他换上新装 找到方向 揭开迷茫 学着坚强 努力去闯!
posts - 20,  comments - 90,  trackbacks - 0

⒈ 用计算机模拟"迷宫问题",求出其中的一条通路.用数组MAZE( 1..M,1..N)表示迷宫,数组元素为1意味着死路,为0表示通路,MAZE(1,1)为迷宫入口,MAZE(M,N)为迷宫出口.设计一个算法判别迷宫问题是否有解,有解则打印出一条路径.

//////大家来做做吧,看起来很有味哦///////

posted on 2006-09-26 12:28 冬天¤不回来 阅读(930) 评论(8)  编辑 收藏 引用

FeedBack:
# re: 趣味试题⒈
2006-09-26 12:41 | beyonlin
深度优先搜索~~  回复  更多评论
  
# re: 趣味试题⒈
2006-09-26 13:01 | 冬天¤不回来
明天给出答案,大家做做撒,写到回复里就行了  回复  更多评论
  
# re: 趣味试题⒈
2006-09-27 19:00 | Optimistic
//本程序求解<迷宫指路>
//By Optimistic

Q1:如何设计程序数据?
A1:一般我们用一个2维数组表示这个迷宫 0代表路 1代表墙

Q2:从A点搜到B点 再搜B点 不又搜到A点了吗?
A1:当我们从A点搜到B点之后 A点就把0改成1 不就变成墙了吗 就不会再搜回去了

Q3:这样不是只能搜到出口 但是不知道具体的路吗?
A1:有两种解决的办法
1.从A点搜到B点 就记录B点的前驱是A 这样我们从出口一路找前驱就可以找到一条路 (本程序采用)
2.我们搜的时候 记录下从入口到此被搜结点的距离 这样我们从出口一路找距离越来越小的结点
也可以找到回入口的路

Q4:要是搜到了边界的0位置怎么办呢?
A1:自然的写法是每次都判断是不是到了边界 不要边界外的子结点
比较有创意的写法是给边界外面加一道围墙 即增设标记为"1"的附加方格(本程序采用)

Q5:...
A1:程序看不懂的地方可以直接来问我... 加油...
*/

#include <stdio.h>

const int M = 8, N = 8; //棋盘的行数 列数(默认为8*8的迷宫 可随意改变)
struct Point
{
int x, y; //方格在棋盘里的行和列
};

struct Queue
{
int front; //队首
int rear; //队尾
Point d[4*M*N]; //元素 这个范围是我想了想定的 应该够了
}Q;

int board[M+2][N+2]; //棋盘
Point start, end; //起点和终点
Point pre[M][N]; //记录结点的前驱
Point offset[4]; //相对位移

bool findPath();
void print();

int main()
{
// freopen("BFS.in", "r", stdin);
offset[0].x = 0, offset[0].y = 1;
offset[1].x = 1, offset[1].y = 0;
offset[2].x = 0, offset[2].y = -1;
offset[3].x = -1, offset[3].y = 0;

int i;
printf("Enter the grid in row-major order:\n");
for(i=1; i<=M; i++)
for(int j=1; j<=N; j++)
scanf("%d", &board[i][j]);
printf("Enter the start position:\n");
scanf("%d%d", &start.x, &start.y);
printf("Enter the end position:\n");
scanf("%d%d", &end.x, &end.y);

if(findPath()) print();
else printf("There is no such road from START to END.\n");

return 0;
}

bool findPath() //搜索从start到end的一条通路 找到返回true 否则返回false
{
if(start.x == end.x && start.y == end.y)
{
pre[end.x][end.y] = end;
return true;
}
//设置棋盘外一圈"围墙"
for(int i=0; i<=M+1; i++)
{
board[0][i] = board[M+1][i] = 1;
board[i][0] = board[i][N+1] = 1;
}

Point cur = start; //current position
Point np = start; //new position

while(1)
{
for(i=0; i<4; i++)
{
np.x = cur.x + offset[i].x;
np.y = cur.y + offset[i].y;
if(board[np.x][np.y] == 0) //通路
{
pre[np.x][np.y] = cur;
if((np.x == end.x) && (np.y == end.y)) break;
Q.d[Q.rear] = np;
Q.rear = (Q.rear+1)%(4*M*N);
board[cur.x][cur.y] = 1;
}
}
if((np.x == end.x) && (np.y == end.y)) break;
if(Q.rear == Q.front) return false;
cur = Q.d[Q.front];
Q.front = (Q.front+1)%(4*M*N);
}
}

void print()
{
printf("One path:\n");
Point ans[M*N];
int ansLen = 0;
Point cur = end;
ans[ansLen++] = cur;
while(cur.x != start.x || cur.y != start.y)
{
cur = pre[cur.x][cur.y];
ans[ansLen] = cur;
ansLen++;
}
int i;
for(i = ansLen-1; i>=0; i--)
{
printf("(%d,%d) ", ans[i].x, ans[i].y);
if((i+1)%5==0) printf("\n");
}
printf("\n");
}
/*
Sample Input:
0 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1
1 0 0 1 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 0 0 1 1 1
1 1 1 1 0 0 1 1
1 1 1 1 1 0 0 1
1 1 1 1 1 1 0 0
1 1
8 8
Sample Output:
One Path:
(1,1) (2,1) (2,2) (3,2) (3,3)
(4,3) (4,4) (5,4) (5,5) (6,5)
(6,6) (7,6) (7,7) (8,7) (8,8)
*/
  回复  更多评论
  
# re: 趣味试题⒈
2006-09-27 19:20 | 冬天¤不回来
厉害.....看来真确答案不用我发了  回复  更多评论
  
# re: 趣味试题⒈
2006-11-09 11:17 | Asp
这个不是CX同学专用版吗?被我发现了……
Optimistic??!!!!!!!!  回复  更多评论
  
# re: 趣味试题⒈
2006-11-11 23:19 | 冬天¤不回来
CX不是OP~~~~  回复  更多评论
  
# re: 趣味试题⒈
2006-11-12 15:58 | 江水兽
@冬天&#164;不回来
@Asp
CX是谁呀?  回复  更多评论
  
# re: 趣味试题⒈
2006-11-13 00:34 | 冬天¤不回来
哈哈你去问问OP就晓得CX是谁拉~~~哈哈哇OHOH  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


QQ:41696402

<2006年9月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(3)

随笔档案

文章档案

Programming

最新随笔

搜索

  •  

积分与排名

  • 积分 - 38464
  • 排名 - 534

最新评论

阅读排行榜

评论排行榜