We have discussed Backtracking and Knight’s tour problem inSet 1. Let us discuss Rat in aMazeas
another example problem that can be solved using Backtracking.
A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. A rat starts from source and has to reach destination. The rat can move only
in two directions: forward and down.
In the maze matrix, 0 means the block is dead end and 1 means the block can be used in the path from source to destination. Note that this is a simple version of the typical Maze problem. For example, a more complex version can be that the rat can move in 4
directions and a more complex version can be with limited number of moves.
Following is an example maze.
Gray blocks are dead ends (value = 0).
Following is binary matrix representation of the above maze.
{1, 0, 0, 0}
{1, 1, 0, 1}
{0, 1, 0, 0}
{1, 1, 1, 1}
Following is maze with highlighted solution path.
Following is the solution matrix (output of program) for the above input matrx.
{1, 0, 0, 0}
{1, 1, 0, 0}
{0, 1, 0, 0}
{0, 1, 1, 1}
All enteries in solution path are marked as 1.
Naive Algorithm
The Naive Algorithm is to generate all paths from source to destination and one by one check if the generated path satisfies the constraints.
while there are untried paths
{
generate the next path
if this path has all blocks as 1
{
print this path;
}
}
Backtrackng Algorithm
If destination is reached
print the solution matrix
Else
a) Mark current cell in solution matrix as 1.
b) Move forward in horizontal direction and recursively check if this
move leads to a solution.
c) If the move chosen in the above step doesn't lead to a solution
then move down and check if this move leads to a solution.
d) If none of the above solutions work then unmark this cell as 0
(BACKTRACK) and return false.
Backtracking 回溯法的三部曲:
1 初始化原始数据,开始点
2 判断下一步是否合法,如果合法就继续递归搜索答案,如果不合法就返回
3 递归直到找到答案,返回真值
这里只需要找到一个解就可以,所以只要找到一个解就可以马上返回。
Leetcode上很喜欢找出所有解的,那么就需要递归所以可能路径了。
说明一下,原题意是规定往下和往右这两个方向探索的,相当于简化了。
这里给出的程序是可以上下左右四个方向探索的,相当于全功能版的解迷宫了,当然,回溯算法是OK的了,类可以继续扩展。
class Maze
{
vector<vector<bool> > maze;
vector<vector<bool> > solMaze;
int row, col;
public:
Maze():maze(6), row(6), col(6), solMaze(6, vector<bool>(6))
{
bool a[6][6] = {
{0,1,0,0,0,0},
{0,0,0,1,1,0},
{1,1,1,0,0,0},
{0,0,0,0,1,1},
{1,1,0,1,0,0},
{0,0,0,0,0,0}};
for (int i = 0; i < 6; i++)
{
maze[i].assign(a[i], a[i]+6);
}
}
bool isLegal(int x, int y)
{
return x>=0 && y>=0 && x<col && y<row && !maze[x][y] && !solMaze[x][y];
}
bool solveMaze(int x, int y)
{
if (x == col-1 && y == row-1)
{
solMaze[x][y] = 1;
return true;
}
if (isLegal(x, y))
{
solMaze[x][y] = 1;
if (solveMaze(x, y+1)) return true;
if (solveMaze(x+1, y)) return true;
if (solveMaze(x-1, y)) return true;
if (solveMaze(x, y-1)) return true;
solMaze[x][y] = 0;
}
return false;
}
void printSolution()
{
for (auto x:solMaze)
{
for (auto y:x)
cout<<y<<" ";
cout<<endl;
}
}
};
int main()
{
cout<<"C++ Class Solution\n";
Maze ma;
ma.solveMaze(0,0);
ma.printSolution();
system("pause");
return 0;
}
分享到:
相关推荐
2022最新版:GEEKS V1.0.10主题:在线学习市场WordPress主题.rar
geeks-for-geeks-solutions:有关Geeks-for-Geeks的问题的解决方案。解决方案可用于C ++
Geeks2TheRescue:使用MERN的Web App,旨在连接雄心勃勃的开发人员
geeks_algorithms 极客算法编码问题
带有React JS的WebApp样板 要求: 确保您使用的是节点版本10 安装软件包: $ npm install 创建一个.env文件: $ cp .env.example .env 开始编码! 以及具有实时重新加载功能的webpack开发服务器(适用于Windows...
夏季极客提交 这个Web应用程序被配制成在Innnovaccer SDE实习分配的一部分,使用的NodeJS,MongoDB的,NodeMailer的电子邮件和Nexmo的手机信息,根据。 预习 报到表格 结帐电子邮件 使用的技术 ...
geeks for geeks上的资源,大家下载下,我攒点几分,呵呵。
欢迎来到4Geeks学院 <\编码时间>内容关于。创始人。团队。奖项。校友关于4Geeks是一家大公司,感觉就像一家小公司;每个人都可以访问,我们喜欢与人接触,我们相信量身定制的教育,而不会离开您的工作,并且100%...
:sparkles: gloomhaven-geeks :sparkles: 这是一个使用Git作为的网站。 它是在不到一分钟的时间内使用创建的。 您可以像这样,或探索一些变体。 如何不同: :artist_palette: 看 :pencil: 内容管理系统 :gear: 静态...
极客换极客 Geeks-For-Geeks 实习文章 使用 scapy 嗅探数据包 - 使用 Javascript 和 DOM 创建棋盘模式 - 如何将链接从一个 iframe 加载到另一个 iframe -
Geeks for Geeks的DSA练习: :
Geeks3D Furmark(OpenGL显卡基准测试工具)V1.17.1 中文官方版
Hardware Hacking Projects for Geeks 英文chm 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或csdn删除
A HashMap for Geeks and normal programmers.
geek极客们都用什么神器,这篇文章给了你答案。
Mac OS X For Unix Geeks 2003
本题的难度并不在最短路径本身这个算法,而是在于堆的操作: 1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高效率,并且这才是有效操作动态地址数据的方法,不用双重指针,我思考了下,觉得更加不好...
Ubuntu for Non-Geeks (Fourth Edition)
Cooking.for.Geeks, hope all programer have good food
UAT-a-Geeks 这是#UAT-a-Geeks League iOT概念证明的官方存储库,使用NodeJS和Arduino