该计划以此为基础它基于以下修改。
(1)指定任意位置(row,col)作为目的地而不是出口(EXIT)寻找路径。
(2)不要使用make[] []数组。
(3)当您第一次到达某个位置时,当在8个方向的相邻位置中存在目的地时,路径搜索结束。
(4)每次都随机确定寻找路径的方向。
校正方法的概要如下。
(1)指定DST_ROW和DST_COL的值而不是EXIT_ROW和EXIT_COL
(2)当转到位置(i,j)时,将迷宫[i] [j]的值从0修改为-1
(3)如果它到达位置(i,j),它检查是否有8个方向相邻位置(DST_ROW,DST_COL)
(4)在回溯中,让我们说(i,j,dV)从堆栈顶部弹出的内容。 dV是表示关于移动方向的信息的方向矢量,并且数据类型是整数。例如,如果dV是41,则它是8位二进制数00101001。每个位可以被称为0位,1位,......,7位来自最低有效位,位0的位0是方向N,位1是方向NE,....位7是方向它对应于西北。比特1表示方向是阻止或已经消失,值0表示尚未尝试方向。在用位置(i,j)回溯之后,从方向矢量的8位的0位指示的方向之一中随机选择尝试的方向。例如,假设dV = 41 = 00101001具有5位0,并且如果选择对应于NW的7位,如果判断移动到NW是合法移动,则移动到该位置,并且在堆栈上移动的值是(i,j,169)。因为8位二进制数10101001是十进制数169。
(A)在所示程序中,编写C代码以填充path()函数中的空白'a'和'b'。
(b)为什么C代码用'a'和'b'写,为什么没有不必要的操作
解释你需要知道和解释的内容。
(c)呈现执行(a)中完成的程序的屏幕,使用的10×10迷宫数据和目的地坐标。 解释你需要解释的内容。
#include "stdafx.h"
#include
#include
#define TRUE 1
#define FALSE 0
#define numRow 10
#define numCol 10
#define DST_ROW 5 // Destination coordinates row
#define DST_COL 6 // Destination coordinates col
#define stack_size 100
typedef struct {
int row; int col; int dir_vector; // See below for a description of the direction vector.
} element;
typedef struct {
short int vert; short int horiz;
} offsets;
void setup_maze();
void set_move();
void path();
int init_dir_vector(int row, int col); // Description in function definition
int get_next_dir(int dir_vector); // Description in function definition
void push(element position);
element pop();
int top = -1;
offsets move[8];
short int maze[numRow + 2][numCol + 2];
element stack[stack_size];
void main() {
setup_maze();
set_move();
path();
}
void setup_maze() {
int i, j;
short int maze0[numRow][numCol] = {
{ 0,0,1,0,1,1,1,0,1,0 },
{ 1,0,0,1,1,1,0,1,0,1 },
{ 1,1,0,1,1,0,1,0,1,1 },
{ 0,0,1,0,1,1,1,0,0,0 },
{ 0,1,1,0,1,0,1,0,1,0 },
{ 1,0,1,1,1,1,0,0,1,0 },
{ 1,1,0,1,0,1,0,0,1,0 },
{ 1,0,0,0,1,0,1,0,0,0 },
{ 0,1,0,1,1,1,0,1,1,0 },
{ 1,0,0,1,1,1,0,0,0,0 }
};
// Inbound coordinates (1,1) are not allowed
if (DST_ROW == 1 && DST_COL == 1) {
printf("\nThe coordinate of destination should be different from that of entrance (1,1).");
exit(0);
}
// Destination is not blocked.
if (maze0[DST_ROW - 1][DST_COL - 1] == 1) {
printf("\nmaze[DST_ROW][DST_COL] should be 0.");
exit(0);
}
for (i = 0; i < numCol + 2; i++) maze[0][i] = 1;
for (i = 0; i < numCol + 2; i++) maze[numRow + 1][i] = 1;
for (i = 0; i < numRow + 2; i++) maze[i][0] = 1;
for (i = 0; i < numRow + 2; i++) maze[i][numCol + 1] = 1;
for (i = 1; i <= numRow; i++)
for (j = 1; j <= numCol; j++) maze[i][j] = maze0[i - 1][j - 1];
}
void set_move() {
move[0].vert = -1; move[0].horiz = 0;
move[1].vert = -1; move[1].horiz = 1;
move[2].vert = 0; move[2].horiz = 1;
move[3].vert = 1; move[3].horiz = 1;
move[4].vert = 1; move[4].horiz = 0;
move[5].vert = 1; move[5].horiz = -1;
move[6].vert = 0; move[6].horiz = -1;
move[7].vert = -1; move[7].horiz = -1;
}
void push(element position) {
stack[++top] = position;
}
element pop() {
element position;
position = stack[top--];
return position;
}
void path() {
int i, row, col, nextRow, nextCol, dir, dir_vector, found = FALSE;
element position;
row = 1; col = 1;
maze[1][1] = -1;
dir_vector = init_dir_vector(1, 1);
if (dir_vector == -1) found = TRUE; //(1,1)의 바로 이웃에 목적지가 있음
else {
top = 0;
stack[0].row = 1; stack[0].col = 1; stack[0].dir_vector = dir_vector;
}
while (top > -1 && !found) {
position = pop();
'A'
while (dir < 8 && !found) {
nextRow = row + move[dir].vert;
nextCol = col + move[dir].horiz;
'B'
}
}
if (found) {
printf("The path is:\n");
printf("row col\n");
for (i = 0; i <= top; i++) printf("%2d%5d\n", stack[i].row, stack[i].col);
printf("%2d%5d\n", row, col);
printf("%2d%5d\n", DST_ROW, DST_COL);
}
else printf("The maze does not have a path\n");
}
int init_dir_vector(int row, int col) {
// input: Position coordinates
// output: -1 or an integer value in the range 0 to 255 (= 2 ^ 8-1)
//
// If there is a destination among eight directional neighbors of a location (row, col), return -1 to terminate the route search,
// If it does not exist, it initializes a direction vector represented by an integer value ranging from 0 to 255 (= 2 ^ 8-1)
//
// direction vector: An 8-bit string expressed as an integer value corresponding to its size
// call bits 0, 1, ..., 7 from the least significant bit
// bit i corresponds to direction i (i = 0, ..., 7). Example: bit 0 is north, bit 1 is north-east, ...
// i bit = 1: direction i indicates that you have already tried in the path finding
// i bit = 0: Indicate that i has not yet visited direction i
// Initialize direction vector of position (row, col): For each of 8 directions of position (row, col), it can not be blocked
// Set the corresponding bit of the direction vector to 1 if it has already gone, otherwise set it to 0.
// How to perform initialization (below code): If all 8 bits are set to 1 and check each direction, reset the corresponding bit to 0
int dir, nextRow, nextCol, dir_vector;
dir_vector = ((int)pow(2.0, 8.0)) - 1; // dir_vector = 255 in decimal, 11111111 in binary (8 bits in all)
for (dir = 0; dir < 8; dir++) {
nextRow = row + move[dir].vert;
nextCol = col + move[dir].horiz;
if (nextRow == DST_ROW && nextCol == DST_COL) return -1; // to report that a path is found
if (!maze[nextRow][nextCol]) dir_vector -= (int)pow(2.0, (double)dir);
}
return dir_vector;
}
int get_next_dir(int dir_vector) {
// input: direction vector (an integer value in the range 0-255 (= 2 ^ 8-1))
// output: direction value 0..7 or 8
//
// Take the integer value representing the direction vector and set the 1 or 0 value of each 8 bits
// Move to an array of size 8 (array d [8] in the code below)
// Randomly selects one of the 0 bits and returns the direction value (0..7) corresponding to that bit
// If there are no 0 bits, return 8 to do backtrack
int dir, d[8], count, k;
for (dir = 0; dir < 8; dir++) {
d[dir] = dir_vector % 2;
dir_vector /= 2;
}
// count = number of 0 bits in direction vector
count = 0;
for (dir = 0; dir < 8; dir++) if (d[dir] == 0) count++;
if (count == 0) return 8;
// Randomly select one of the count 0 bits and return the corresponding direction value (0..7)
k = rand() % count + 1;
for (dir = 0; dir < 8; dir++) {
if (d[dir] == 0) k--;
if (k == 0) return dir;
}
}