Submission #52864852

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define endl '\n'
using namespace std;
const int N = 1e3 + 233;
int h,w,ans = -1;
int f[N][N];
bool vis[N][N];
int fx[4] = {1,-1,0,0};
int fy[4] = {0,0,1,-1};
char ch[N][N]; 
int dfs(int x,int y){
  int ans = 0; 
  
  if(f[x][y]) return f[x][y];
    
  for(int i=0;i<4;i++)
    for(int j=0;j<4;j++)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define endl '\n'
using namespace std;
const int N = 1e3 + 233;

int h,w,ans = -1;
int f[N][N];
bool vis[N][N];
int fx[4] = {1,-1,0,0};
int fy[4] = {0,0,1,-1};
char ch[N][N]; 

int dfs(int x,int y){
	int ans = 0; 
	
	if(f[x][y]) return f[x][y];
		
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			if(ch[x+fx[i]][y+fy[i]] == '#')
				return 1;
				
	for(int i=0;i<4;i++){
		int nx = x + fx[i];
		int ny = y + fy[i];
		if(1<=nx&&nx<=h && 1<=ny&&ny<=w && ch[nx][ny] == '.' && !vis[nx][ny]){
			vis[nx][ny] = 1;
			ans += dfs(nx,ny);
			vis[nx][ny] = 0;
				
		}
	}
//	cout<<x<<" "<<y<<" "<<ans<<endl;
	return f[x][y] = ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cin>>h>>w;
	
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>ch[i][j];
		}
	}
	
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(ch[i][j] == '.'){
//				cout<<i<<" "<<j<<" "<<dfs(i,j)<<endl;
				ans = max(ans , dfs(i,j)); 
			}
		}
	}
	
	cout<<ans;
	
	return 0;
}

Submission Info

Judge Result