小d和超级泡泡堂(牛客）

题目描述

小 DDD 在某天醒来发现自己穿越到了小游戏《超级泡泡堂》的世界，他得到了一份地图，一个技能和三个提示。

这个地图共有 nnn 行 mmm 列，行从上到下按 111 ~ nnn 编号，列从左到右按 111 ~ mmm 编号。地图上存在空地、石头、杂草。

这个技能是在自己当前所在位置放置一个不会对自己造成影响的炸弹，炸弹爆炸会产生火焰，火焰会向上下左右四个方向蔓延，如果火焰的蔓延方向上为空地，则会直接蔓延到空地并且在空地上开始继续蔓延，如果火焰的蔓延方向上为杂草，则会将杂草烧掉使其变为空地， 并且在新产生的空地继续蔓延，如果火焰蔓延方向上为石头，则无法继续朝这个方向蔓延，当然，火焰不可能蔓延到地图外。

三个提示分别是:

1、你可以向上下左右四个方向移动，如果那个方向上不是石头且不会移动到地图外。

2、你的技能只能使用一次。

3、你只有正确回答你最多能通过使用技能使多少杂草地变为空地才能够回到现实世界。

小 DDD 非常想要回去现实世界玩原神，请你帮助他计算出他最多能通过使用技能使多少杂草地变为空地。

注:当火焰蔓延到另一个地方将要继续蔓延时，蔓延方式等同于在该地方重新放置炸弹。 \textbf{ 注:当火焰蔓延到另一个地方将要继续蔓延时，蔓延方式等同于在该地方重新放置炸弹。 } 注:当火焰蔓延到另一个地方将要继续蔓延时，蔓延方式等同于在该地方重新放置炸弹。

输入描述:

第一行包含两个整数 n,m(1≤n,m≤1000)n, m(1\leq n,m\leq 1000)n,m(1≤n,m≤1000)。

接下来 nnn 行每行 mmm 个字符，其中 '.' 表示空地，'#' 表示石头，‘!' 表示杂草，‘@’ 表示小 DDD 当前所处位置。

输出描述:

输出一行包含一个整数表示他最多能通过使用技能使多少杂草地变为空地。

示例1

输入

复制4 4 ..!. .@.# !##! #!!!

4 4

..!.

.@.#

!##!

#!!!

输出

复制2

2

#include <iostream>
using namespace std;
static char A[1000][1000];
int cnt = 0;
void dfs(char A[1000][1000],int i,int j,int n,int m){
    if(i<0||j<0||i>=n||j>=m||A[i][j]=='#'||A[i][j]=='F'){
        return ;
    }
    if(A[i][j]=='!'){
        cnt++;
        A[i][j] = 'F';
    }
    A[i][j] = 'F';
    dfs(A,i-1,j,n,m);
    dfs(A,i,j-1,n,m);
    dfs(A,i+1,j,n,m);
    dfs(A,i,j+1,n,m);
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 0;i < n; i++){
        for(int j = 0;j < m; j++){
            cin>>A[i][j];
        }
    }
    for(int i = 0;i < n; i++){
        for(int j = 0;j < m; j++){
            if(A[i][j]=='@'){
                dfs(A,i,j,n,m);
            }
        }
    }
    cout<<cnt;
    return 0;
}

dfs求解。