mongster 2019-04-24 23:14
浏览 396

c语言,迷宫问题,救救孩子

该计划以此为基础它基于以下修改。
(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;

}

}

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题