//本程序求解<迷宮指路>
//By Optimistic
Q1:如何設(shè)計(jì)程序數(shù)據(jù)?
A1:一般我們用一個(gè)2維數(shù)組表示這個(gè)迷宮 0代表路 1代表墻
Q2:從A點(diǎn)搜到B點(diǎn) 再搜B點(diǎn) 不又搜到A點(diǎn)了嗎?
A1:當(dāng)我們從A點(diǎn)搜到B點(diǎn)之后 A點(diǎn)就把0改成1 不就變成墻了嗎 就不會(huì)再搜回去了
Q3:這樣不是只能搜到出口 但是不知道具體的路嗎?
A1:有兩種解決的辦法
1.從A點(diǎn)搜到B點(diǎn) 就記錄B點(diǎn)的前驅(qū)是A 這樣我們從出口一路找前驅(qū)就可以找到一條路 (本程序采用)
2.我們搜的時(shí)候 記錄下從入口到此被搜結(jié)點(diǎn)的距離 這樣我們從出口一路找距離越來(lái)越小的結(jié)點(diǎn)
也可以找到回入口的路
Q4:要是搜到了邊界的0位置怎么辦呢?
A1:自然的寫法是每次都判斷是不是到了邊界 不要邊界外的子結(jié)點(diǎn)
比較有創(chuàng)意的寫法是給邊界外面加一道圍墻 即增設(shè)標(biāo)記為"1"的附加方格(本程序采用)
Q5:...
A1:程序看不懂的地方可以直接來(lái)問(wèn)我... 加油...
*/
#include <stdio.h>
const int M = 8, N = 8; //棋盤的行數(shù) 列數(shù)(默認(rèn)為8*8的迷宮 可隨意改變)
struct Point
{
int x, y; //方格在棋盤里的行和列
};
struct Queue
{
int front; //隊(duì)首
int rear; //隊(duì)尾
Point d[4*M*N]; //元素 這個(gè)范圍是我想了想定的 應(yīng)該夠了
}Q;
int board[M+2][N+2]; //棋盤
Point start, end; //起點(diǎn)和終點(diǎn)
Point pre[M][N]; //記錄結(jié)點(diǎn)的前驅(qū)
Point offset[4]; //相對(duì)位移
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;
}
//設(shè)置棋盤外一圈"圍墻"
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)
*/
回復(fù) 更多評(píng)論