POJ2446 다이어그램 최대 일치
14272 단어 poj
분석:
흑백이 엇갈리는 방법으로 바둑판을 두 개의 점집으로 나누고 1*2의 카드로 전체 덮어쓰기를 이분도와 완전히 일치시킬 수 있는지 여부.
AC 코드
1 //Memory: 172K Time: 32MS
2 #include <iostream>
3 #include <cstring>
4 #include <cstdio>
5
6 using namespace std;
7
8 const int maxn = 32 * 32 / 2 + 10;
9 int maze[33][33];
10 int edge[maxn][4];
11 int ne[maxn];
12 int match[maxn];
13 int vis[maxn];
14 int m, n, k;
15 int x, y;
16 int flag;
17 int num1, num0;
18 const int s[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
19
20
21 bool findPath(int start)
22 {
23 for (int i = 0; i < ne[start]; i++){
24 int current = edge[start][i];
25 if ( vis[current] ) continue;
26 vis[current] = 1;
27 if ( !match[current] || findPath( match[current] ) ){
28 match[current] = start;
29 return true;
30 }
31 }
32 return false;
33 }
34
35 bool solve()
36 {
37 memset(match, 0, sizeof(match));
38 int cnt = 0;
39 for (int i = 1; i <= num0; i++){
40 memset(vis, 0, sizeof(vis));
41 if ( findPath(i) )
42 ++cnt;
43 }
44 if (cnt == num0) return true;
45 return false;
46 }
47
48 void input()
49 {
50 memset(edge, 0, sizeof(edge));
51 memset(ne, 0, sizeof(ne));
52 memset(maze, 0, sizeof(maze));
53 scanf("%d%d%d", &m, &n, &k);
54 for (int i = 0; i < k; i++){
55 scanf("%d%d", &x, &y);
56 maze[y - 1][x - 1] = -1;
57 }
58 num0 = num1 = 0;
59 for (int i = 0; i < m; i++)
60 for (int j = 0; j < n; j++){
61 if ( maze[i][j] != -1 && (i + j) % 2 == 0) {
62 maze[i][j] = ++num0;
63 }
64 else if (maze[i][j] != -1 && (i + j) % 2 == 1) {
65 maze[i][j] = ++num1;
66 }
67 }
68 if ( num0 != num1 ) return;
69 for (int i = 0; i < m; i++) {
70 for (int j = 0; j < n; j++){
71 if ( (i + j) % 2 == 0 && maze[i][j] != -1){
72 int current = maze[i][j];
73 for (int k = 0; k < 4; k++){
74 int ni = i + s[k][0];
75 int nj = j + s[k][1];
76 if (ni >= m || ni < 0 || nj >= n || nj < 0)
77 continue;
78 if ( maze[ni][nj] != -1) edge[current][ne[current]++] = maze[ni][nj];
79 }
80 }
81 }
82 }
83 }
84
85 int main()
86 {
87 input();
88 if ( num0 == num1 && solve() ) printf("YES
");
89 else printf("NO
");
90 return 0;
91 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.