weixin_39765887 2021-12-28 22:09 采纳率: 0%
浏览 63

八数码问题深度优先搜索中的一个小问题

img

img

img

img


为什么做了一个i++,我的路径池就全变成0了?
我的完整代码如下:


#include <iostream>
using namespace std;
#define MAX_TIMES 100

int start[3][3] = { 2,8,3,1,6,4,7,9,5 };             //初始状态
int finish[3][3] = { 1,2,3,8,9,4,7,6,5 };            //目标状态
int locate[2];                                       //locate数组存放空格所在的行列数
int counts = 0;
struct road                                  
{
    int step[6] = { 0 };
};
road all_road[500];                                  //路径池存放走过的路径
int now_road[6] = { 0 };                             //当前路径
int last_dir = 0;                                    //上一步的方向
void locate_space()                                  //初始化locate数组
{
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (start[i][j] == 9)
            {
                locate[0] = i; locate[1] = j;
            }
        }
    }
}
void show_locate()
{
    cout << "空格位置为:";
    cout << locate[0] << " " << locate[1] << endl;
}
void show()
{
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cout << start[i][j];
        }
        cout << endl;
    }
    cout << endl;
}
void go_left()
{
    int tmp;
    tmp = start[locate[0]][locate[1]];
    start[locate[0]][locate[1]] = start[locate[0]][locate[1] - 1];
    start[locate[0]][locate[1] - 1] = tmp;
    locate[1]--;
}
void go_right()
{
    int tmp;
    tmp = start[locate[0]][locate[1]];
    start[locate[0]][locate[1]] = start[locate[0]][locate[1] + 1];
    start[locate[0]][locate[1] + 1] = tmp;
    locate[1]++;
}
void go_up()
{
    int tmp;
    tmp = start[locate[0]][locate[1]];
    start[locate[0]][locate[1]] = start[locate[0] - 1][locate[1]];
    start[locate[0] - 1][locate[1]] = tmp;
    locate[0]--;
}
void go_down()
{
    int tmp;
    tmp = start[locate[0]][locate[1]];
    start[locate[0]][locate[1]] = start[locate[0] + 1][locate[1]];
    start[locate[0] + 1][locate[1]] = tmp;
    locate[0]++;
}
bool compare()
{
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (start[i][j] != finish[i][j])
            {
                return 0;
            }
        }
    }
    return 1;
}
bool compare_step(int depth,int l,int k)
{

        now_road[depth + 1] = k;
        for (int j = 0; j <= depth + 1; j++)
        {
            if (all_road[l].step[j] != now_road[j])
            {
                now_road[depth + 1] = 0;
                return 0;
            }
        }
        now_road[depth + 1] = 0;
        return 1;

}
bool compare_road(int depth,int k,int i)
{
    for (int l = 0; l <= i; l++)
    {
        if (compare_step(depth, l, k) == 1)
            return 1;
    }
    return 0;
}
void goback(int depth)
{
    if (now_road[depth] == 1)
    {
        go_right();
        return;
    }
    else if (now_road[depth] == 2)
    {
        go_down();
        return;
    }
    else if (now_road[depth] == 3)
    {
        go_left();
        return;
    }
    else if (now_road[depth] == 4)
    {
        go_up();
        return;
    }
    else
    {
        cout << "出错" << endl;
        return;
    }

}
void show_all_road(int i)
{
    cout << "路径池:" << endl;
    for (int j = 0; j <= i; j++)
    {
        for (int k = 0; k < 6; k++)
        {
            cout << all_road[i].step[k];
        }
        cout << endl;
    }
    cout << endl;
}
void show_now_road()
{
    cout << "当前路径:" << endl;
    for (int i = 0; i < 6; i++)
    {
        cout << now_road[i];
    }
    cout << endl;
}
void dfs()
{
    int i = 0;
    int depth = 0;
    while (counts < MAX_TIMES) 
    {
        while (depth < 5)
        {
            if (locate[1] > 0 && compare_road(depth, 1, i) != 1 && last_dir != 3)
            {
                go_left();
                last_dir = 1;
                depth++; 
                now_road[depth] = 1;
                all_road[i].step[depth] = 1;
                show_locate();
                show();
                show_all_road(i);
                show_now_road();
                cout << endl;
                if (compare() == 1)
                {
                    cout << "搜索成功" << endl;
                    cout << "搜索次数为:" << counts << endl;
                    return;
                }
                break;
            }
            else if (locate[0] > 0 && compare_road(depth, 2, i) != 1 && last_dir != 4)
            {
                go_up();
                last_dir = 2;
                depth++;
                now_road[depth] = 2;
                all_road[i].step[depth] = 2;
                show_locate();
                show();
                show_all_road(i);
                show_now_road();
                cout << endl;
                if (compare() == 1)
                {
                    cout << "搜索成功" << endl;
                    cout << "搜索次数为:" << counts << endl;
                    return;
                }
                break;
            }
            else if (locate[1] < 2 && compare_road(depth, 3, i) != 1 && last_dir != 1)
            {
                go_right();
                last_dir = 3;
                depth++;
                now_road[depth] = 3;
                all_road[i].step[depth] = 3;
                show_locate();
                show();
                show_all_road(i);
                show_now_road();
                cout << endl;
                if (compare() == 1)
                {
                    cout << "搜索成功" << endl;
                    cout << "搜索次数为:" << counts << endl;
                    return;
                }
                break;
            }
            else if (locate[0] < 2 && compare_road(depth, 4, i) != 1 && last_dir != 2)
            {
                go_down();
                last_dir = 4;
                depth++;
                now_road[depth] = 4;
                all_road[i].step[depth] = 4;
                show_locate();
                show();
                show_all_road(i);
                show_now_road();
                cout << endl;
                if (compare() == 1)
                {
                    cout << "搜索成功" << endl;
                    cout << "搜索次数为:" << counts << endl;
                    return;
                }
                
                break;
            }
            else
            {
                
                cout << "goback1" << endl;
                goback(depth);
                show_locate();
                show();
                last_dir = now_road[depth - 1];
                now_road[depth] = 0;
                depth--;
                show_all_road(i);
                show_now_road();
                i++;
                
                cout << "i = "<< i << endl;
                
                for (int n = 0; n <= depth; n++)
                {
                    all_road[i].step[n] = all_road[i - 1].step[n];
                }
                cout << endl;
                break;
            }
        }
        if (depth == 5)
        {
            cout << "goback2" << endl;
            goback(depth);
            show_locate();
            show();
            last_dir = now_road[depth - 1];
            now_road[depth] = 0;
            depth--;
            show_all_road(i);
            show_now_road();
            i++;
            
            cout << "i = " << i << endl;
            for (int n = 0; n <= depth; n++)
            {
                all_road[i].step[n] = now_road[n]; 
            }
            cout << endl;
            
        }
    }
}
int main()
{
    locate_space();
    show_locate();
    show();
    dfs();
    
}

  • 写回答

2条回答 默认 最新

  • 关注

    你先执行 i++; 再调用 show_all_road(i); 传递的i就是加1之后的

    如果 i 到了数组最后一个元素下标.你先执行 i++; 再调用 show_all_road(i); 传递的i加1不就数组越界了

    评论 编辑记录

报告相同问题?

问题事件

  • 创建了问题 12月28日

悬赏问题

  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)