- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
DFS是一种深度搜索算法,它的特点是"不撞南墙不回头",运用递归对不同方向的结果进行搜索.
这是一个迷宫游戏,有一个n×n的矩阵,矩阵内只能有 # 或 . 这两种字符,如果是 # 则是墙,如果是 . 则是可以走的路。起点是左上角,终点是右下角,每次只能往上、下、左、右四个方向走。 请你写一个程序,判断这个迷宫是否可以从起点走到终点.
第1行一个整数n,代表矩阵大小为n×n。 第2~n+1行输入n×n的迷宫矩阵。 输出此迷宫是否能从起点走到终点,可以输出 yes ,不可以输出 no .
5
..##.
#..##
..###
.####
.....
yes
5
..###
...##
..##.
##...
.##..
no
用 char 类型的二维数组 maze 存储输入的迷宫矩阵,用 int 类型的二维数组 visited 存储走过的地方,再用 int 类型的变量 flag 记录是否走完迷宫, flag 初始值设为0, visited 所有元素初始值设为0, maze 与 visited 的下标是对应的,如果 maze 中的地方是 # ,则可以将 visited 相同下标元素的值设为1,再深度搜索可能的情况,若判断成功走到终点,则将 flag 设为1并结束递归.
#include <bits/stdc++.h>
using namespace std;
char maze[105][105];
int visited[105][105],flag=0,n;
void dfs(int x,int y)//递归搜索函数
{
if(x==n-1&&y==n-1)//走到终点的特判条件
{
flag = 1;
return ;
}
else
{
if(!visited[x-1][y]&&x-1>=0)//上
{
visited[x-1][y] = 1;
dfs(x-1,y);
}
if(!visited[x+1][y]&&x+1<=n-1)//下
{
visited[x+1][y] = 1;
dfs(x+1,y);
}
if(!visited[x][y-1]&&y-1>=0)//左
{
visited[x][y-1] = 1;
dfs(x,y-1);
}
if(!visited[x][y+1]&&y+1<=n-1)//右
{
visited[x][y+1] = 1;
dfs(x,y+1);
}
}
}
int main()
{
cin >> n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin >> maze[i][j];
if(maze[i][j]=='#')
{
visited[i][j] = 1;
}
}
}
if(visited[0][0]==1||visited[n-1][n-1]==1)
{
cout << "no" << endl;
return 0;
}
dfs(0,0);
if(flag==1) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}
最后此篇关于C++深度优先搜索(DFS)讲解的文章就讲到这里了,如果你想了解更多关于C++深度优先搜索(DFS)讲解的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我正在使用python 2.7 当我尝试在其上运行epsilon操作时出现此错误, 这是我的代码 import cv2 import numpy as np img = cv2.imread('img
1 很多程序员对互联网行业中广泛讨论的“35岁危机”表示不满,似乎所有的程序员都有着35岁的职业保质期。然而,随着AI技术的兴起,这场翻天覆地的技术革命正以更加残酷且直接的方式渗透到各行各业。程序员
我有一个包含多个子模块的项目,我想列出每个子模块的相对深度 该项目: main_project submodule1 submodule1\submodule1_1 submo
我有一张彩色图像及其深度图,它们都是由 Kinect 捕获的。我想将它投影到另一个位置(以查看它在另一个视角下的样子)。由于我没有 Kinect 的内在参数(相机参数);我该如何实现? P.S:我正在
给出了这三个网址: 1) https://example.com 2) https://example.com/app 3) https://example.com/app?param=hello 假
这个着色器(最后的代码)使用 raymarching 来渲染程序几何: 但是,在图像(上图)中,背景中的立方体应该部分遮挡粉红色实体;不是因为这个: struct fragmentOutput {
我希望能够在 ThreeJS 中创建一个房间。这是我到目前为止所拥有的: http://jsfiddle.net/7oyq4yqz/ var camera, scene, renderer, geom
我正在尝试通过编写小程序来学习 Haskell...所以我目前正在为简单表达式编写一个词法分析器/解析器。 (是的,我可以使用 Alex/Happy...但我想先学习核心语言)。 我的解析器本质上是一
我想使用像 [parse_ini_file][1] 这样的东西。 例如,我有一个 boot.ini 文件,我将加载该文件以进行进一步的处理: ;database connection sett
我正在使用 Mockito 来测试我的类(class)。我正在尝试使用深度 stub ,因为我没有办法在 Mockito 中的另一个模拟对象中注入(inject) Mock。 class MyServ
我试图在调整设备屏幕大小时重新排列布局,所以我这样做: if(screenOrientation == SCREEN_ORIENTATION_LANDSCAPE) { document
我正在 Ubuntu 上编写一个简单的 OpenGL 程序,它使用顶点数组绘制两个正方形(一个在另一个前面)。由于某种原因,GL_DEPTH_TEST 似乎不起作用。后面的物体出现在前面的物体前面
static FAST_FUNC int fileAction(const char *pathname, struct stat *sb UNUSED_PARAM, void *mo
我有这样的层次结构: namespace MyService{ class IBase { public: virtual ~IBase(){} protected: IPointer
我正在制作一个图片库,需要一些循环类别方面的帮助。下一个深度是图库配置文件中的已知设置,因此这不是关于无限深度循环的问题,而是循环已知深度并输出所有结果的最有效方法。 本质上,我想创建一个 包含系统中
如何以编程方式在树状结构上获取 n 深度迭代器?在根目录中我有 List 每个节点有 Map> n+1 深度。 我已修复 1 个深度: // DEPTH 1 nodeData.forEach(base
我正在构建一个包含大量自定义元素的 Polymer 单页界面。 现在我希望我的元素具有某种主样式,我可以在 index.html 或我的主要内容元素中定义它。可以这样想: index.html
我正在尝试每 25 秒连接到配对的蓝牙设备,通过 AlarmManager 安排,它会触发 WakefulBroadcastReceiver 以启动服务以进行连接。设备进入休眠状态后,前几个小时一切正
假设有一个有默认值的函数: int foo(int x=42); 如果这被其他人这样调用: int bar(int x=42) { return foo(x); } int moo(int x=42)
是否可以使用 Javascript 获取 url 深度(级别)? 如果我有这个网址:www.website.com/site/product/category/item -> depth=4www.w
我是一名优秀的程序员,十分优秀!