一笔画猫游戏辅助器DFS

本文主要是介绍一笔画猫游戏辅助器DFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

一、DFS基础

https://blog.csdn.net/sandalphon4869/article/details/89345189

二、C++代码一阶

1.图片：

2.转化成矩阵

0代表通道，1代表无路

0 0 0 0
1 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0

3.输入

n行m列
矩阵
起点位置：1行1列
终点位置：1行4列

终点位置：得自己判断在哪

5 4
0 0 0 0
1 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
1 1
1 4

4.输出

W：往上
A：往左
S：往下
D：往右
#：墙
o：终点

******************路径1******************
D S # o
# S W #
S A W A
S D S W
D W D W

对应

5.代码

#include<iostream>
#include<stack>
using namespace std;int maze[10][10];//1和0的迷宫矩阵
int vis[10][10];//记录迷宫中的某个位置是否访问过
char direct[10][10];//WASD的方向结果矩阵
int n,m;int ox,oy;	//起点位置
int ex,ey;	//终点位置int points=0;	//记录所遍历的点的数量int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};//四个方向struct point//位置
{int x,y;
} p;stack<point> path,temp;//记录路径,temp是一个临时变量，和path一起处理路径int count;//路径条数void dfs(int x,int y)//x,y:当前位置
{if(x==ex-1 && y==ey-1)//成功---下面处理路径问题{if(path.size()!=points)	//必须走完所有的点，而不是抄捷径{return ;}cout << "******************路径"<< ++count <<  "******************" << endl;while(!path.empty())//将path里面的点取出来，放在temp里面{//path从栈顶-栈底的方向，路径是从终点-起点的顺序point p1 = path.top();path.pop();temp.push(p1);}point lastnode;while(!temp.empty()){//输出temp里面的路径，这样刚好是从起点到终点的顺序point p1 = temp.top();temp.pop();path.push(p1);//将路径放回path里面，因为后面还要回溯!!!if(path.size()==points){direct[p1.x][p1.y]='o';}else if(path.size()>1){if(p1.x-lastnode.x==1){direct[lastnode.x][lastnode.y]='S';//下}else if(p1.x-lastnode.x==-1){direct[lastnode.x][lastnode.y]='W';//上}else if(p1.y-lastnode.y==1){direct[lastnode.x][lastnode.y]='D';//右}else if(p1.y-lastnode.y==-1){direct[lastnode.x][lastnode.y]='A';//左}}lastnode.x=p1.x;lastnode.y=p1.y;}//输出WASD矩阵for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<direct[i][j]<<' ';}cout<<endl;}return;}if(x<0 || x>=n || y<0 || y>=m)//越界return;//如果到了这一步，说明还没有成功，没有出界for(int i=0;i<4;i++)//从4个方向探测{int nx = x + dir[i][0];int ny = y + dir[i][1];//nx,ny：选择一个方向，前进一步之后，新的坐标//条件：nx,ny没有出界，maze[nx][ny]=0这个点不是障碍可以走，vis[nx][ny]=0说明(nx,ny)没有访问过，可以访问if(0<=nx && nx<n && 0<=ny && ny<m && maze[nx][ny]==0 && vis[nx][ny]==0){vis[nx][ny]=1;//设为访问过p.x = nx;p.y = ny;path.push(p);//让当前点进栈dfs(nx,ny);//进一步探测vis[nx][ny]=0;//回溯path.pop();//由于是回溯，所以当前点属于退回去的点，需要出栈}}
}int main()
{count = 0;cin >> n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){direct[i][j]='#';vis[i][j] = 0;cin >> maze[i][j];if(maze[i][j]==0){points++;}}}cin>>ox>>oy;cin>>ex>>ey;vis[ox-1][oy-1]=1;p.x = ox-1;p.y = oy-1;path.push(p);//起点先入栈dfs(ox-1,oy-1);return 0;
}

二、C++

这篇关于一笔画猫游戏辅助器DFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---