入门

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

59

提示

数据规模与约定

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

算法1

(暴力dfs)

利用每个点可以往上下左右四个方向移动进行dfs

此处的dfs无需进行回溯,因为题目中说了每个瓷砖可以被重复走过,但不能被重复计数.
如果我们回溯st[a][b] = false , 则会出现重复计数的问题

在一个瓷砖反复横跳是没意义的,因为每个瓷砖只能被计数一次,所以我们可以将每个瓷砖都走过了作为递归的出口

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 30;
bool st[N][N];
char road[N][N];
int w,h;    //w列 ; h行
int cnt = 1;
//每个点可以往上下左右四个方向移动
int move_x[4] = {-1 , 1 , 0 , 0};
int move_y[4] = {0 , 0 , -1 , 1};

void dfs(int x , int y)
{
    for(int i = 0; i < 4; i++)
    {
        int a = x + move_x[i];
        int b = y + move_y[i];

        if(st[a][b]) continue;

        if(a>0 && b>0 && a<=h && b<=w && road[a][b]!='#')
        {
            cnt++;
            st[a][b] = true;
            dfs(a , b);
        }
    }
}

int main()
{
    cin>>w>>h;
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++)
            cin>>road[i][j];


    //获取初始时的第一块瓷砖
    int x , y;
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++)
            if(road[i][j] == '@')
            {
                st[i][j] = true;
                dfs(i , j);
            }

    cout<<cnt<<endl;

    return 0;
}