首页 > 代码库 > 深度优先和广度优先的基础应用
深度优先和广度优先的基础应用
图来自啊哈算法
这里描述的问题就是如何从1,1走到4,3
这里有两个解决方案,一个是用深度优先算法
初始化地图,和标记点
int[,] ditu = new int[5, 4]{ {0,0,1,0}, {0,0,0,0}, {0,0,1,0}, {0,1,0,0}, {0,0,0,1} }; int[,] book_1 = new int[5, 4];
定义每次走的方向
int[,] fanxiang = new int[4, 2] { {0,1},//右边 {1,0},//下边 {0,-1},//左边 {-1,0}//上边 };
private void dyzdlj(int x, int y, int step) { if (x == 3 && y == 2) { if (step < min) { min = step; } Console.WriteLine("我找到了一种走的方法了,一共走了{0}步", step); return; } for (int i = 0; i < 4; i++) { //走 int tx = x + fanxiang[i, 0]; int ty = y + fanxiang[i, 1]; //判断是否越界 if (tx < 0 || ty < 0 || tx > 4 || ty > 3) { continue; } if (book_1[tx, ty] == 0 && ditu[tx, ty] == 0) { book_1[tx, ty] = 1; dyzdlj(tx, ty, step + 1); book_1[tx, ty] = 0; } } }
2.广度搜索,所谓的广度搜索呢,就是每次把能走的全部走光
定义基本的结构,用来保存数据
public struct node { public int x;//x坐标 public int y;//y坐标 public int s;//步数 }
具体实现
private void gdyxsf() { node[] nn = new node[20]; int head = 0, tail = 0; //设置起点 nn[head].x = 0; nn[head].y = 0; nn[head].s = 0; book_1[0, 0] = 1; tail++; int flag = 0; while (head<tail) { for (int i = 0; i < 4; i++) { int tx =nn[head].x+fanxiang[i, 0]; int ty = nn[head].y + fanxiang[i, 1]; if (tx<0||ty<0||tx>4||ty>3) { continue; } //判断地图是否被走过 if (ditu[tx,ty]==0&&book_1[tx,ty]==0) { book_1[tx, ty] = 1; nn[tail].x = tx; nn[tail].y = ty; nn[tail].s = nn[head].s + 1; tail++; } if (book_1[3,2]==1) { flag = 1; break; } } if (flag==1) { Console.WriteLine("我已经到了这个地方了,我一共走了{0}步", nn[tail - 1].s); break; } head++; } }
执行结果
深度优先和广度优先的基础应用
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。