深度优先算法（DFS）洛谷P1683-入门

虽然洛谷是有题解的,但是你如果直接看得懂题解,你也不会来看这篇文章..

这些代码均是我记录自身成长的记录,有写的不好的地方请谅解！

先上代码：

#include <iostream>  
#include <vector>  
#include<iomanip>
#include<cstdio>
using namespace std;
const int N = 30;
char g[N][N];
int n,m;//n行 m列
int zhuankuai = 0;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };//方向
bool cizhuan[N][N];//同位标记瓷砖是否能走 全局静态数组默认false
void dfs(int x, int y) {for (int i = 0; i < 4; i++) {int a = x + dx[i], b = y + dy[i];	//上右下左历遍if (a < 0 || a >= n || b < 0 || b >= m) continue;//边界不走if (g[a][b] != '.') continue;//如果它不是瓷砖 也不走if (cizhuan[a][b]) continue;//走过的瓷砖 爷不走//通过考验cizhuan[a][b] = true;//走过你了 下次不走了zhuankuai++;//走过的砖块数++dfs(a,b);//递归 继续走下去 当走到条件尽头 无路可走后就停下了}
}
int main() { scanf("%d %d", &m, &n);for (int i = 0; i < n; i++) {scanf("%s", g[i]);}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (g[i][j] == '@') {cizhuan[i][j] = true;dfs(i, j);}}}zhuankuai++;//起点也算一块砖printf("%d\n", zhuankuai);return 0;
}

开始来一步步解析做法：

1.建立数组g[N][N]，为什么N=30？ 因为题目中给出了范围要求,而我的N=30会比题目大一些,防止莫名其妙的问题.

2.为什么选用char类型数组,请看题目给出的样例,他就是一个个字符...

3.scanf("%s", g[i]);如何解释这一行代码？ 注意,我的for循环i是从0开始到n-1的,这么做是可以直接根据样例输入数据的.

4.注意n它代表行 m它代表列 所以scanf("%d %d", &m, &n);的意思是 先输入 列 再输入 行,看到这里你应该就能理解[3]了,它是字符以行的形式录入的.

5.双For循环是为了找到起始点的坐标[i][j]

6.找到起始位置‘@’之后我们也同时找到了它的坐标,那么,建立一个DFS函数,把它的坐标先传进去,由此,我们获得了DFS最开始的起始.

7.如何解释 cizhuan[i][j]=true? 它（bool cizhuan）代表了每个砖块是否被踩过,因为洛谷题目中告诉我们重复踩砖块是不算计数的,而我把它定义在全局区就是让他默认False状态,代表没被踩过,当你传入这个坐标进入DFS（深度优先）的时候,它就被踩过了,所有标记为true.

8.双for循环结束后,为什么要zhuankuai+1？ 因为起始点被踩过了,这在dfs函数内是没有记录的,所以你需要+1.

====================main部分结束===================DFS部分↓

首先我们定义了两个数组 dX 和 dY ,你需要把它们连起来看.

        比如你有1个坐标{x,y}，这里请不要把它想象成数学的坐标系,计算机的数组坐标它不一样,具体的,你自己可以创建一个数组,自己拿手指指它们的坐标,如果你自己说不出来,请先回去好好学习一下二维数组.

        当你理解二维数组的坐标后,再看dx和dy,然后再结合初始的（x,y）,你会发现如果同时引入dx的第一个元素 和 dy的第一个元素 那么初始的(x,y)就成为了→(x-1,y+0) , 这代表什么？ 如果你把(x,y)作为一个点,那么这个坐标的意思就是在计算机的二维数组中往右边挪移了一个单位，由此我们实现了点的四向移动.

        我们拥有了四个方向移动的方法之后,我们就需要建立一个for循环来历遍这3个方向,这里我创建了int类型的a和b,它们分别代表在这一个方向上x和y被更新成了什么坐标.

        我们获得a,b这2个新的坐标,我们遇到了一个问题---这个坐标是否可用？

        所以我们首先需要判断是否越界,代码中用一个if已经囊括了,注意：请不要忘记n代表行,m代表列！！！注意数组是从0行0列开始计数的！！！

        然后我们遇到了第二个问题,这个砖是不是能走的砖？它可能是墙壁！所以我们要判断，如果它不是'.'就跳过（换个方向继续试）. 这里这个‘.'在题目中的含义是可走的砖头.

        最后我们需要判断,这个可以走的砖头有没有被走过,这时候我们之前定义的bool数组就可以出来判断了,如果它是True(走过)那么这个方向仍然不能走,我们还需要转到下一个方向,反之,它可以走,那么我就走它！然后把它定义成false代表走过了,这时候对走过的砖块即（zhuankuai)就可以进行++的操作了,代表走过一块儿.

        然后因为这个坐标通过了我们的层层考验,所以我们需要把这个坐标重新传入DFS函数中,这里牵扯到一点递归的概念,当这个DFS函数结束的时候,代表已经没有砖块可以走了,至此,我们走过了最多的瓷砖,并且没有死,OK,题目通关！

        如果你不想看来回切屏看题目,没事,我已经帮你复制下来了！A.A

        

题目描述

不是任何人都可以进入桃花岛的，黄药师最讨厌像郭靖一样呆头呆脑的人。所以，他在桃花岛的唯一入口处修了一条小路，这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩，我们认为是安全的，而有的瓷砖一踩上去就会有喷出要命的毒气，那你就死翘翘了，我们认为是不安全的。你只能从一块安全的瓷砖上走到与他相邻的四块瓷砖中的任何一个上，但它也必须是安全的才行。

由于你是黄蓉的朋友，她事先告诉你哪些砖是安全的、哪些砖是不安全的，并且她会指引你飞到第一块砖上（第一块砖可能在任意安全位置），现在她告诉你进入桃花岛的秘密就是：如果你能走过最多的瓷砖并且没有死，那么桃花岛的大门就会自动打开了，你就可以从当前位置直接飞进大门了。

注意：瓷砖可以重复走过，但不能重复计数。

输入格式

第一行两个正整数 WW 和 HH，分别表示小路的宽度和长度。

以下 HH 行为一个 H×WH×W 的字符矩阵。每一个字符代表一块瓷砖。其中，. 代表安全的砖，# 代表不安全的砖，@ 代表第一块砖。

输出格式

输出一行，只包括一个数，即你从第一块砖开始所能安全走过的最多的砖块个数（包括第一块砖）。

输入输出样例

输入 #1复制

11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........

输出 #1复制

59

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤W,H≤201≤W,H≤20。