P1683 入门

入门

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

59

提示

数据规模与约定

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

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 25;
char g[N][N];
bool st[N][N];
int res = 1; // 起点
int n, m;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int x, int y){
    
    for (int i = 0; i < 4; i ++){
        int a = x + dx[i];
        int 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);
    }
}

int main(){
    cin >> 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);
            }
        }
    }
    
    cout << res << endl;
    
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

queue<PII> q;

const int N = 25;
char g[N][N];
bool st[N][N];
int res = 1; // 起点
int n, m;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};


void bfs(int x, int y){
    q.push({x, y});
    
    while(q.size() > 0){
        auto t = q.front(); // 队首
        q.pop();
        
        for (int i = 0; i < 4; i ++){
            int a = t.first + dx[i];
            int b = t.second + 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 ++;
            q.push({a, b});
        }
        
    }
}

int main(){
    cin >> 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;
                bfs(i, j);
            }
        }
    }
    
    cout << res << endl;
    
    return 0;
}