抱歉,您的瀏覽器無法訪問本站
本頁面需要瀏覽器支持(啟用)JavaScript
了解詳情 >

計算機程式設計1 的作業5 – 走迷宮

題目簡述

  • 有一4×4迷宮,起點在(0,0),終點在(3,0)

  • 迷宮中可能會有障礙物

  • 從起點到終點,每一格都需走過剛好一遍

    題目輸出

  • 印出總共有幾種走法

解題想法

  • 迷宮並沒有很大
    可利用深度優先搜尋法(Depth First Search)把整個地圖走過

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*****************************************
Filename:cp1_hw5.c
Author:Willy Chen(willychen.org)
Date:2018.01.26
*****************************************/
#include<stdio.h>
#include<stdbool.h>
#define ROW 4+1
#define COLUMN 4+1

void DFS(bool maze[COLUMN][ROW],int *path,int x,int y,int start){
/* jumps out-of-bounds */
if(x<0||y<0||x==COLUMN-1||y==ROW-1)
return;
/* check all the places have been jumped */
if(x==3&&y==0){
int count=0;
for(int i=0;i<ROW-1;i++){
for(int j=0;j<COLUMN-1;j++){
if(maze[i][j]==false)
count++;
}
}
if(!count){
(*path)++;
return;
}
return;
}
/* the place has been jumped */
if(maze[x][y]==true&&start==true)
return;
maze[x][y]=true;

/* jumps up, down, right, left */
DFS(maze,path,x+1,y,true);
DFS(maze,path,x-1,y,true);
DFS(maze,path,x,y+1,true);
DFS(maze,path,x,y-1,true);

if(maze[x][y]==true&&start==true)
maze[x][y]=false;

return;
}

int main(){
bool maze[COLUMN][ROW]={0};

/* input the map */
for(int i=0; i<COLUMN; i++){
for(int j=0; j<ROW; j++){
maze[i][j]=false;
}
}

/* obstacle location */
int x,y;
while(scanf("%d,%d",&x,&y)!=EOF){
maze[x][y]=true;
}
maze[0][0]=true;
maze[3][0]=true;

int path =0;
/* calculate the paths */
DFS(maze,&path,0,0,false);

printf("path:%d\n",path);
return 0;
}

評論




本站使用 Volantis 作為主題