題目:
maze.png
如圖所示,有一個6 * 6的迷宮,左上角為入口抱完,右下角為出口醉锅。圖中0的位置可以走宫仗,1的位置不能走。請編程找出唯一的一條通過迷宮的路。
解題思路:
1.初始化迷宮:(對二維數(shù)組)首先在首尾行各加一行‘1’,首尾列各加兩列‘1’(目的為了后面函數(shù)四個方向判斷時可以將每個數(shù)都用一般情況處理)
2.函數(shù)設(shè)計:
使用遞歸汰瘫,對每個數(shù)進行判斷。通過循環(huán)擂煞,如果i,j能變到6,6混弥,則成功找到路徑,否則沒有对省。其中蝗拿,當(dāng)走到每條死路時,值變?yōu)?再調(diào)回蒿涎;正確路徑則變?yōu)?1蛹磺;返回success
3.主函數(shù):輸出二維數(shù)組,但用特殊符號顯示迷宮
4.對是否找到路徑進行判斷同仆;如果有則用控制輸出迷宮,對其中不同值進行不同符號輸出裙品,顯示路徑
源碼:
#include<stdio.h>
int visit(int i,int j);
int success=0;
int startI=1,startJ=1;
int endI=6,endJ=6;
int maze[8][8]=
{
{1,1,1,1,1,1,1,1},
{1,0,1,0,1,1,1,1},
{1,0,0,0,1,0,1,1},
{1,0,1,1,0,0,0,1},
{1,0,1,1,0,1,0,1},
{1,0,0,0,0,1,0,1},
{1,0,1,0,1,1,0,1},
{1,1,1,1,1,1,1,1},
};
void main()
{
int i,j;
printf("\n顯示迷宮:\n");//顯示迷宮
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(maze[i][j]==1) //值為1時設(shè)置為障礙
printf("█");
if(maze[i][j]==0) //值為0時俗批,可以通過
printf(" ");
}
printf("\n");
}
//調(diào)用函數(shù)俗或,判斷是否找到路徑
if(visit(startI,startJ)==0)
{
printf("\n沒有出口\n");
}
else
{
printf("\n顯示路徑:\n"); //如果找到則顯示路徑
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(maze[i][j] == 1)
printf("█");
else
if(maze[i][j] == -1)
printf("◇");
else
printf(" ");
}
printf("\n");
}
}
}
int visit(int i, int j)
{
maze[i][j] = -1;
if(i == endI && j == endJ) //如果能到達出口,返回ture
{
success = 1;
}
if(success != 1 && maze[i][j+1] == 0) //判斷右側(cè)是否為0
visit(i, j+1);
if(success != 1 && maze[i+1][j] == 0) //判斷下側(cè)是否為0
visit(i+1, j);
if(success != 1 && maze[i][j-1] == 0) //判斷左側(cè)是否為0
visit(i, j-1);
if(success != 1 && maze[i-1][j] == 0) //判斷上側(cè)是否為0
visit(i-1, j);
if(success != 1)
maze[i][j] = 0;
return success;
}
執(zhí)行結(jié)果:
maze.jpg
總結(jié):
1.首先拿到題沒思路岁忘,問題歸結(jié)練習(xí)少了
2.有了思路后辛慰,但是代碼還是無法實現(xiàn)。以上用的遞歸干像,但自己也不能運用帅腌,只會單純的公式遞歸,說明自己的遞歸有問題麻汰。問題為遞歸做少了速客,但最大的問題在于對遞歸的理解不到位,導(dǎo)致有思路但是回到代碼也無法下手
3.代碼實現(xiàn)能力有待增強