温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

回溯法解决迷宫问题

发布时间:2020-05-30 18:09:34 来源:网络 阅读:742 作者:清秋冷 栏目:编程语言

现在有迷宫地图:(回溯法)

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

0 0 0 1 1 1 1 1 1 1

1 1 0 1 1 1 1 1 1 1

1 1 0 1 1 1 1 1 1 1

1 1 0 1 1 1 1 1 1 1

1 1 0 0 0 0 0 0 1 1

1 1 0 1 1 1 1 0 1 1

1 1 0 1 1 1 1 0 1 1

1 1 0 1 1 1 1 1 1 1

  将迷宫地图存于文件中,将文件里的信息依次读入到二维数组中,设置入口,先将其压栈,然后将其设置为2,以便于进行回溯操作,然后进行上下左右这四个方位的试探,如果试探到这个地方的值为0就满足条件,先将其压栈,再将其置为2,依次类推。如果第一次没有找到通路则进行回溯操作,直到找到通路。

#define N 10

using namespace std;

struct Pos

{

int _row;

int _col;

};


void GetMaze(int* arr,int n)//将二维数组改成一维数组形式使用

{

FILE* fp=fopen("MazeMap.txt","r");

assert(fp);

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n;)

{

char ch = fgetc(fp);

if (ch == '1' || ch == '0')

{

arr[i*n + j] = ch-'0';

j++;

}

else

{

continue;

}

}

}

}

void PrintMaze(int* arr, int n)

{

for(int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

cout << arr[i*n + j] << " ";

}

cout << endl;

}

}

bool Isviable(int* arr, int n, Pos cur, int row,int col)//检查相应位置是否为0

{

if (arr[n*row + col] == 0 && row < n&&row >= 0 && col < n&&col >= 0)

{

return true;

}

else

{

return false;

}

}

bool GetPath(int* arr,int n,const Pos& entry,stack<Pos>& path)

{

Pos cur = entry;

path.push(cur);

while (!path.empty())

{

arr[cur._row*n + cur._col] = 2;//将走过的路径置为2

if (cur._row == n - 1)

{

return true;

}

//上

Pos next = cur;

next._row--;

if (Isviable((int*)arr, n, next, next._row, next._col))

{

cur = next;

path.push(cur);

continue;

}


//下

next = cur;

next._row++;

if (Isviable((int*)arr, n, next, next._row, next._col))

{

cur = next;

path.push(cur);

continue;

}

//左

next = cur;

next._col--;

if (Isviable((int*)arr, n, next, next._row, next._col))

{

cur = next;

path.push(cur);

continue;

}

//右

next = cur;

next._col++;

if (Isviable((int*)arr, n, next, next._row, next._col))

{

cur = next;

path.push(cur);

continue;

}

return false;

cur = path.top();//回溯

path.pop();

}

return false;//原路返回,并检测出没有通路

}

/***************************************/

void testMaze()

{

int arr[N][N] = {};

GetMaze((int*)arr, N);//将二维数组转换成一维数组操作

PrintMaze((int*)arr, N);

stack<Pos> path;

Pos entry = { 2, 0 };//开始入口地方

cout<<GetPath((int*)arr, N,entry,path)<<endl;

PrintMaze((int*)arr, N);

}

回溯法解决迷宫问题

可以进行别的方案解决,递归法

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI