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
| #include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000)
#define MAXK (32)
#define bh(i, j) ((((i) - 1) * MAXK) + (j))
using namespace std;
const int xy[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
struct edg {
int from, to, next;
} b[MAXN * 4 + 5];
int g[MAXN * 2 + 5], cntb, n, m, link[MAXN * 2 + 5], ans, kk;
bool fbd[MAXN + 5], vis[MAXN * 2 + 5];
void ade(int fr, int t) {
++cntb;
b[cntb].from = fr, b[cntb].to = t, b[cntb].next = g[fr];
g[fr] = cntb;
}
bool find(int x) {
for (int i = g[x]; i; i = b[i].next)
if (!vis[b[i].to]) {
vis[b[i].to] = true;
if (!link[b[i].to] || find(link[b[i].to])) {
link[b[i].to] = x;
return true;
}
}
return false;
}
int main() {
scanf("%d%d%d", &m, &n, &kk);
for (int i = 1, xi, yi; i <= kk; i++) {
scanf("%d%d", &xi, &yi);
fbd[bh(xi, yi)] = true;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 0; k < 4; k++) {
int ni = i + xy[k][0], nj = j + xy[k][1];
if (i + xy[k][0] <= n && j + xy[k][1] <= m && i + xy[k][0] > 0 && j + xy[k][1] > 0 && !fbd[bh(i, j)] && !fbd[bh(ni, nj)])
ade(bh(i, j), bh(ni, nj));
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
memset(vis, false, sizeof(vis));
if (find(bh(i, j)))
++ans;
}
puts((ans == n * m - kk) ? "YES" : "NO");
return 0;
}
|