地、颜色、魔法
鏈接：https://ac.nowcoder.com/acm/contest/218/A
來源：牛客網(wǎng)
牛客練習(xí)賽11.16
? ?現(xiàn)在，你作為一名新星鵬洛客，找到了一塊絕佳的修煉地。這塊地方可以被描述成一個(gè) n x m 的矩形。你已經(jīng)在這塊地中的一些位置打好了標(biāo)記。接下去，就該對(duì)整塊地賦予你的顏色了。一個(gè)位置能被賦予你的顏色，當(dāng)且僅當(dāng)滿足以下條件之一：
? ? ? ?1. 這個(gè)位置被打上了標(biāo)記。
? ? ? ?2. 這個(gè)位置在不經(jīng)過被打標(biāo)記的位置的情況下與邊界不連通（這個(gè)圖是四聯(lián)通的）。換句話說，如果你從這個(gè)位置開始，在不經(jīng)過被打標(biāo)記的位置，且只能向上下左右四個(gè)方向移動(dòng)的情況下永遠(yuǎn)不能走到地圖的邊界，那么這個(gè)位置符合條件。
? ? ? ?現(xiàn)在，你的好基友想知道，你能為多少個(gè)位置賦予你自己的顏色呢？
輸入描述:
第一行包含兩個(gè)正整數(shù) n, m ，表示地圖的長(zhǎng)和寬。 接下去 n 行，每行一個(gè)長(zhǎng)為 m 的字符串，表示地圖的一行。 其中? 表示該位置未被打標(biāo)記； 表示該位置被打了標(biāo)記。 保證地圖僅由??和 ?構(gòu)成。輸出描述:
輸出僅一行，包含一個(gè)整數(shù)，表示你的答案。?
示例1
輸入
復(fù)制
4 4 .... .### .#.# .###輸出
復(fù)制
9說明
?可以被賦予顏色的位置在下圖中用? 標(biāo)出了。
備注:
1 ≤ n x m ≤ 106-----------------------------------
題意就是上面內(nèi)個(gè)（不好懂是吧） hh
題意大概就是讓你把一塊不與外面聯(lián)通的區(qū)域（這塊區(qū)域被‘#’包圍）或“#”格涂色，問涂得塊數(shù)個(gè)數(shù)
如果從正面考慮的話得從這塊不與外面聯(lián)通的區(qū)域里的‘.’開始搜 ，判斷是否與外面聯(lián)通，但其實(shí)可以直接從圖四周邊界搜不是“#”的塊比如‘ . ’和 被‘ # ’包圍的‘.’聯(lián)通區(qū)域（因?yàn)楸槐弧?# ’包圍的‘.’不會(huì)被搜到（自己想一下））標(biāo)記成其他字符 如 @，最后在跑一邊圖把不是@的塊數(shù)累加即為結(jié)果。
-------->注意得用vector存圖 ，數(shù)組不夠（我就是不會(huì)vector存圖，沒做出來....今天才學(xué)的vector存圖，補(bǔ)的題）
代碼如下：
#include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<iostream> #include<stdlib.h> #include<vector> using namespace std; const int inf=0x3f3f3f3f; const int maxn=1000000; vector<char>e[maxn]; int dx[]={0,0,-1,1}; int dy[]={1,-1,0,0}; int n,m; bool judge(int x,int y){if(x<0||x>=n||y<0||y>=m||e[x][y]=='#'||e[x][y]=='@')return false;return true; } void dfs(int x,int y){ e[x][y]='@';for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(judge(nx,ny)){dfs(nx,ny);}} } int main(){scanf("%d%d",&n,&m);char x;for(int i=0;i<n;i++){getchar();for(int j=0;j<m;j++){scanf("%c",&x);e[i].push_back(x);}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(i==0||i==n-1){if(e[i][j]=='.'){dfs(i,j); }}if((j==0&&i!=0)||(j==0&&i!=n-1)||(j==m-1&&i!=0)||(j==m-1&&i!=n-1)){if(e[i][j]=='.'){dfs(i,j); } }} }int ans=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(e[i][j]!='@'){ans++;}}}cout<<ans<<endl; return 0; }自己的一個(gè)特別智障的地方
bool judge(int x,int y){if(x<0||x>=n||y<0||y>=m||e[x][y]=='#'||e[x][y]=='@')return false;return true; }判斷是否能往下搜的條件，我是從反面考慮的，剛開始沒注意到（沒這個(gè)條件e[x][y]=='@'）當(dāng)經(jīng)過某點(diǎn)“ . ”改為‘ @ ’后，其他點(diǎn)搜是再經(jīng)過此點(diǎn)是會(huì)一直搜，死遞歸...
如果不考慮那么多的話 直接 ：
bool judge(int x,int y){if(x>=0&&x<n&&y>=0&&y<m&&e[x][y]=='.')return true;return false; }?
?
?
總結(jié)
