为什么做了一个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();
}