Python与C++代码制作深度优先遍历动画模拟蚂蚁走受限迷宫所有线路的程序

萍乡C++编程

这个程序需要sprites模块才能运行，如果没有安装，请用pip install sprites进行安装。

"""
在5行6列的迷宫中,小蚂蚁在(0,0)处.但是它的腿受伤了,
只能在最左上端,也就是行列号(0,0)处,
每次往下或者往右前进一格,那么到达右下端,就是行列号(4,5)处,共有多少种走法?
本程序需要sprites库支持，如果没有安装，请用cmd命令打开管理员，输入
pip install sprites进行安装。不会请联系本人微信：scratch8
"""
from sprites import Sprite

def output(): #  输出路径
    s = ""
    cnt = 0
    for i,j in path[:-1]:
        s = s + f"({i},{j})->"
        cnt = cnt + 1
        if cnt ==5:s = s + "\n"
    s = s + f"({path[-1][0]},{path[-1][1]})"
    zi.write(s,align='center',font=('',16 ,'normal'))
    
def move_sprite():
    zi.clear()    
    zi.goto(0,230)
    zi.write('第'+str(pen.counter)+'条线路',align='center',
             font=('宋体',18,'bold'))
    zi.goto(0,170)
    output()
    pen.clear()
    pen.wait(1)    
    for i,j in path:
        pen.goto(cors[i][j])
        if not pen.isdown():pen.down()
        pen.dot(10,'blue')
        pen.wait(0.1)
    pen.up()
    pen.wait(1.1)
    
def dfs(r,c):  # (r,c)是所到达的行列号
    if r==rows-1 and c==cols-1: # 如果到达终点
        pen.counter += 1        
        move_sprite()  # 根据path描述移动画笔
    else:
        for dr,dc in [(0,1),(1,0)]:# 右，下
            next_row = r + dr      # 下行
            next_col = c + dc      # 下列            
            # 如果超出范围，则跳过
            if next_row<0 or next_row>=rows or \
               next_col<0 or next_col>=cols:continue
            path.append((next_row,next_col))  # 记录路径上的点
            dfs(next_row,next_col)
            path.pop()  # 回溯到上一格(将继续选择下一个方向)        
        
path = [ ]
rows,cols = 5,6      # 行列数
bug = Sprite()       # 新建角色，用于画格子
bug.pensize(4)
bug.pencolor('blue')
# 画5行，6列格子，50x50，返回所有格子坐标点
cors = bug.draw_grid2(5,6,60,60)
# 下面只是让角色遍历格子，for循环可以去掉
for row in cors:
    for x,y in row:
        bug.goto(x,y)
        bug.wait(0.02)
bug.goto(cors[0][0])
bug.bk(22);bug.addy(5);bug.write((0,0))

bug.goto(cors[rows-1][cols-1])
bug.bk(22);bug.addy(5);bug.write((rows-1,cols-1))
bug.hide()

# 写字的角色
zi = Sprite(visible=False)
zi.goto(0,230)

# 写说明的角色
tt = Sprite(visible=False)
tt.goto(0,280); tt.color('blue')
s = "深 度 优 先 遍 历 迷 宫 ，\n只向右或向下，向右优先。"
tt.write(s,align='center',font=('黑体',22,'normal'))
tt.goto(0,-220); tt.color('magenta')
s = "根据组合数学，所有线路条数是:\nmath.comb(9,5)=126"
tt.write(s,align='center',font=('',18,'normal'))
tt.goto(0,-280); tt.color('purple')
s = "作者：李兴球，博客：www.lixingqiu.com"
tt.write(s,align='center',font=('楷体',15,'normal'))

pen = Sprite(visible=False)
pen.color('red')
pen.width(2)
pen.counter = 0   # 自定义属性，用于计数
path.append((0,0))
dfs(0,0)

下面的C++代码没有加上GUI库，所以不会有显示界面，只会输出线路条数。

#include 
#include 
using namespace std;
int rows, cols;
int counter = 0;
vector<pair<int, int>> path;
void move_sprite() {        //移动画笔画线路 
    // 实现移动画笔的逻辑，可以用C++的一些GUI库实现。 
}

void dfs(int r, int c) {
    if (r == rows - 1 && c == cols - 1) { // 如果到达终点
        counter++;  move_sprite();     // 根据path描述移动画笔
    } else {        
        int dr[] = {0, 1};  // 定义两个方向：右和下
        int dc[] = {1, 0};
        for (int i = 0; i < 2; i++) {
            int next_row = r + dr[i];
            int next_col = c + dc[i];
            // 如果超出范围，则跳过
            if (next_row < 0 || next_row >= rows ||
			next_col < 0 || next_col >= cols) continue; 
			path.push_back({next_row, next_col}); // 记录路径上的点
            dfs(next_row, next_col);
            path.pop_back(); // 回溯到上一格(将继续选择下一个方向)
        }
    }
}

int main() {
    rows = 5;   //行数 
    cols = 6;   //列数
    path.push_back({0, 0}); // 起点
    dfs(0, 0);
    cout << "总共的路径数量: " << counter << endl;
    return 0;
}

关注本公众号输入mayimaze可下载本程序源代码及素材与gif动图。

本程序在本人“异编程”微信公众号上有相关文章，网址：https://mp.weixin.qq.com/s/jrLirJd7luDxyeF7uEu_mg