入门

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

59

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq W,H\le 20$。

思路：
通过深度优先搜索（DFS）算法来遍历给定二维字符数组（模拟地图场景）中特定区域的功能。具体来说，它从给定的起点（标记为@）开始，在地图上只能沿着.字符所代表的路径进行遍历，统计能够到达的.字符的数量，最后输出包括起点在内能够到达的总位置数量。

代码展示：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;
const int N = 30;
char g[N][N];
int dx[] = { -1,0,1,0 };//上右下左
int dy[] = { 0,1,0,-1 };
bool st[N][N];//存每块瓷砖走没走过
int res = 0;//记录走过的瓷砖数
//当前访问到坐标（x,y)
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 (st[a][b]) continue;//如果走过就不走了
		st[a][b] = true;
		res++;
		dfs(a, b);
		//st[a][b]=false为什么不回溯呢？前一个点能走，保证上一个点走过
//注意：瓷砖可以重复走过，但不能重复计数。
	}
}
int main()
{
	scanf("%d%d", &m, &n);//注意这里先取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] == '@')
			{
				st[i][j] = true;
				dfs(i, j);
			}
		}
	}
	res++;//加上起点
	printf("%d", res);
	return 0;
}