UVa 12876 - City

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

現在給定格子狀的街區,每一個街區只會與垂直、水平的相鄰街區有通行的人行道。現在已知每個街區有多少人行道,求未知的街區人行道數量情況。

Sample Input

1
2
3
4
5
1
3 3
2 2 3
1 -1 3
1 1 0

Sample Output

1
1

Solution

二分圖黑白染色,知道每一個只會與相鄰上下左右的街區相鄰,那麼就像國際象棋一樣的黑白染色,相鄰的人行道一定只會連接於黑跟白之間。

分別計算黑和白的 degree 總數,差的絕對值就是未知街區的答案。

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
inline int readchar() {
const int N = 1048576;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int testcase, n, m, x;
// scanf("%d", &testcase);
ReadInt(&testcase);
while (testcase--) {
// scanf("%d %d", &n, &m);
ReadInt(&n);
ReadInt(&m);
int odd = 0, even = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// scanf("%d", &x);
ReadInt(&x);
if (x == -1) continue;
if ((i+j)&1)
odd += x;
else
even += x;
}
}
printf("%d\n", abs(odd - even));
}
return 0;
}
/*
1
3 3
2 2 3
1 -1 3
1 1 0
*/