Yester07
2022-07-01 16:31
采纳率: 50%
浏览 61

八数码(华容道)BFS算法的一个BUG

八数码(华容道)BFS算法:
问题:
我的代码输入了之后运行不出来,可能是某个地方出了问题,求改正!
我给的测试用例是:
123456780
234567801
运行结果如下:

img

可能是int* p和int* s用的不对,我不确定
下面是我的代码:

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef int state[9];
state st[36288], goal;  //用于存储状态
int dist[36288]={0};  //距离数组
int father[36288];
static int total_count = 0;
static int best_count = 0;
const int dx[4] = { -1,1,0,0 };//上下左右移的操作
const int dy[4] = {0,0,-1,1};
int head[10003], next[10003];
int cnt = 0;
void init_lookup_table()
{
    memset(head,0,sizeof(head));
}
int hash(state p)  //hash散列
{
    int v = 0;
    for (int i = 0; i < 9; i++)
        v = v * 10 + p[i];
    return v % 10003;
}
int try_to_insert(int s)
{
    int h = hash(st[s]);
    int u = head[h];
    while (u)
    {
        if (memcmp(st[u], st[s], sizeof(st[s])))
            return 0;
        u = next[u];
    }
    next[s] = head[h];
    head[h] = s;
    return 1;
}
int BFS()
{
    init_lookup_table();
    int front = 1;  //st[0]不用
    int rear = 2;
    while (front < rear)
    {
        int* p = st[front];
        if (memcmp(goal, p, sizeof(p)) == 0)  //判断是否和目标状态重合
            return front;
        int z = 0;
        while (z < 9)
        {
            if (!p[z])
                break;
            z++;
        }
        int x = z / 3, y = z % 3;  //获取0在二维数组中的下标位置
        for (int d = 0; d < 4; d++)  //算出0在新的二维数组中的位置
        {
            int newx = x + dx[d];
            int newy = y + dy[d];
            int newz = newx * 3 + newy;  //算出0在新的一维数组中的位置
            if ((newx >= 0 && newx < 3) && (newy >= 0 && newy < 3))  //判断0在新的二维数组中的位置是否合法
            {
                int* t = st[rear];
                memcpy(t, p, sizeof(p));  //将图拷贝到新的位置
                t[newz] = p[z];  //改变0的位置
                t[z] = p[newz];
                dist[rear] = dist[front] + 1;  //记录新状态相较初始位置移动的步数
                father[rear] = front;
                if (try_to_insert(rear))
                {
                    rear++;
                    cnt++;
                    printf("-------------------------\n");
                    printf("%d %d %d\n", t[0], t[1], t[2]);
                    printf("%d %d %d\n", t[3], t[4], t[5]);
                    printf("%d %d %d\n", t[6], t[7], t[8]);
                    printf("目前已经走了%d步", cnt);
                    printf("-------------------------\n");
                }
            }
        }
        front++;
    }
}

int main()
{
    printf("请输入初始状态的一维数组:");
    for (int i = 0; i < 9; i++)  //读取初始状态
        scanf("%d", &st[1][i]);
    printf("请输入目标状态的一维数组:");
    for (int i = 0; i < 9; i++)  //读取目标状态
        scanf("%d", &goal[i]);
    int ans = BFS();  //获取目标状态的下标
    if (ans > 0)
        printf("%d", dist[ans]);  //输出目标状态到初始状态的距离
    else
        printf("无法到达目标状态\n");
    return 0;
}

我是对照以下代码敲得,因为C语言没有引用,所以只能自己改

img

img

img

img

1条回答 默认 最新

相关推荐 更多相似问题