链接:https://ac.nowcoder.com/acm/contest/218/A
来源:牛客网

题目描述

红色来源于山脉,象征着狂躁、愤怒、混乱,血雨腥风,电光火石。
蓝色来源于海岛,象征着控制、幻觉、诡计,运筹帷幄,谋定后动。
绿色来源于树林,象征着生命、蛮力、成长,横冲直撞,生生不息。
黑色来源于沼泽,象征着死亡、贪婪、腐败,追求卓越,不计代价。
白色来源于平原,象征着秩序、公平、正义,携手共进,稳中求胜。

       现在,你作为一名新星鹏洛客,找到了一块绝佳的修炼地。这块地方可以被描述成一个 n x m 的矩形。你已经在这块地中的一些位置打好了标记。接下去,就该对整块地赋予你的颜色了。一个位置能被赋予你的颜色,当且仅当满足以下条件之一:
       1. 这个位置被打上了标记。
       2. 这个位置在不经过被打标记的位置的情况下与边界不连通(这个图是四联通的)。换句话说,如果你从这个位置开始,在不经过被打标记的位置,且只能向上下左右四个方向移动的情况下永远不能走到地图的边界,那么这个位置符合条件。
       现在,你的好基友想知道,你能为多少个位置赋予你自己的颜色呢?

输入描述:

第一行包含两个正整数 n, m ,表示地图的长和宽。
接下去 n 行,每行一个长为 m 的字符串,表示地图的一行。
其中  表示该位置未被打标记; 表示该位置被打了标记。
保证地图仅由  和  构成。

输出描述:

输出仅一行,包含一个整数,表示你的答案。

示例1

输入

4 4
....
.###
.#.#
.###

输出

9
1 ≤ n x m ≤ 10

一个很基础的搜索算法,换一种搜索方法,从边界开始搜索,遍历一遍就行了

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int d[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
string s[maxn];
int ans=0;
int n,m;
void dfs(int x,int y){
    if(s[x][y]=='#')
        return ;
    s[x][y]='#';
    ans++;
    for(int i=0;i<4;i++){
        int dx=x+d[i][0];
        int dy=y+d[i][1];
        if(dx>=0 && dx<n && dy>=0 && dy<n){
            if(s[dx][dy]=='.')
                dfs(dx,dy);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    for(int i=0;i<n;i++){
        dfs(i,0);
        dfs(i,m-1);
    }
    for(int i=0;i<m;i++){
        dfs(0,i);
        dfs(n-1,i);
    }
    cout<<n*m-ans<<endl;
    system("pause");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注