Submission #74279308

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,char> pic;
typedef vector<int> vi;
typedef vector<ll> vll;
#define SZ(x) ((int)x.size())
ll ksm(ll a,ll b,ll p){if (p == 1)return 0;if (b == 0)return 1%p;
ll ans = 1;	a %= p;while (b > 0){if (b&1){ans = ans*a%p;}a = (a*a)
%p;b >>= 1;}return ans;}
const int mod = 1e9+7;
const int P = 998244353;
const ll inf = (1LL << 50LL);
const ll N = 5010;

const int D[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int h,w,ans = 0;
bool dist[1010][1010];
char s[1010][1010];
inline void dfs(int x,int y){
	dist[x][y] = true;
	for (int i = 0;i < 4;i++){
		int nx = x+D[i][0],ny = y+D[i][1];
		if (!dist[nx][ny] && s[nx][ny] == '.'){
			dfs(nx,ny);
		}
	}
}
int main(){
	scanf("%d%d",&h,&w);
	for (int i = 1;i <= h;i++){
		scanf("%s",s[i]+1);
	}
	for (int i = 0;i <= h+1;i++){
		for (int j = 0;j <= w+1;j++){
			if (i <= 0 || i > h || j <= 0 || j > w){
				s[i][j] = '.';
			}
		}
	}
	dfs(0,0);
	for (int i = 1;i <= h;i++){
		for (int j = 1;j <= w;j++){
			if (s[i][j] == '.' && !dist[i][j]){
				ans++;
				dfs(i,j);
			} 
		}
	}
	printf("%d",ans);
	
    return 0;
}

Submission Info

Judge Result