-
Notifications
You must be signed in to change notification settings - Fork 0
/
1990.cpp
98 lines (76 loc) · 1.66 KB
/
1990.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//solution by Wsl_F
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define pb(x) push_back(x)
#define F(i,j) ( ( (i)-1 )*m + (j)-1 )
const int MaxN= 100;
int next_[MaxN*MaxN+100];
bool used[MaxN*MaxN+100];
int board[MaxN+10][MaxN+10];
vi g[MaxN*MaxN+100];
bool try_kuhn (int v)
{
if (used[v]) return false;
used[v] = true;
for (int i=0; i<g[v].size(); i++)
{
int to = g[v][i];
bool f= (next_[to] == -1);
if (!f) f= try_kuhn(next_[to]);
if (f)
{
next_[to] = v;
return true;
}
}
return false;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int n,m,a,b;
cin>>n>>m;
char c;
int empt= 0;
memset(board,-1,sizeof(board));
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
{
cin>>c;
if (c=='.') { board[i][j]= 0; empt++; }
else board[i][j]= 1;
}
if (empt%2)
{
cout<<"NO"<<endl;
return 0;
}
for (int i=1; i<=n; i++)
for (int j= 1; j<=m; j++)
if (board[i][j]==0 && ((i&1)==(j&1)))
{
int u= F(i,j);
{
if (board[i][j-1]==0) g[u].pb(u-1);
if (board[i][j+1]==0) g[u].pb(u+1);
if (board[i-1][j]==0) g[u].pb(u-m);
if (board[i+1][j]==0) g[u].pb(u+m);
}
}
int sum= 0;
memset(next_,-1,sizeof(next_));
for (int i=1; i<=n; i++)
for (int j= 1; j<=m; j++)
if (board[i][j]==0 && ((i&1)==(j&1)))
{
memset(used,0,sizeof(used));
if (try_kuhn(F(i,j))) sum++;
}
if (sum*2==empt) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}