File: Timus 1035. Cross-stitch
Author: xiaotian @ hnu
Created on 2010年9月30日, 上午9:06
题解：把网格交叉点抽象成顶点，正面线抽象为正边，反面的抽象为反边。
求联通块，分别求出每个联通块的针数，最后相加即为答案。
1 #include<iostream>
2 #include<stdio.h>
3 #include<string.h>
4 #include<queue>
5 using namespace std;
6 int p[40500], a[40500][2], sum[40500], n, m;
7
8 int find(int x) {
9 if (p[x] != x)p[x] = find(p[x]);
10 return p[x];
11 }
12
13 int judge(int x, int y) {
14 return find(x) == find(y);
15 }
16
17 void make(int side) {
18 int ul, ur, dl, dr;
19 char c;
20 for (int i = 0; i < n; i++)
21 {
22 for (int j = 0; j <= m; j++) {
23 scanf("%c", &c);
24 if (j == m) break;
25 ul = i * (m + 1) + j;
26 ur = ul + 1;
27 dl = (i + 1)*(m + 1) + j;
28 dr = dl + 1;
29 if ((c == 'X') || (c == '\\')) {
30 a[ul][side]++;
31 a[dr][side]++;
32 if (!judge(ul, dr))p[p[ul]] = p[dr];
33 }
34 if ((c == 'X') || (c == '/')) {
35 a[ur][side]++;
36 a[dl][side]++;
37 if (!judge(ur, dl))p[p[ur]] = p[dl];
38 }
39 }
40 }
41 }
42
43 int main() {
44 while (scanf("%d%d\n", &n, &m) != EOF) {
45 int i, ans = 0;
46 for (i = 0; i < (m + 1)*(n + 1); i++) p[i] = i;
47 make(0);
48 make(1);
49 for (i = 0; i < (m + 1)*(n + 1); i++)
50 if (a[i][0] || a[i][1]) sum[find(i)] += abs(a[i][0] - a[i][1]);
51 for (i = 0; i < (m + 1)*(n + 1); i++)
52 if ((a[i][0] || a[i][1]) && (p[i] == i)) ans += sum[i] ? sum[i] / 2 : 1;
53 printf("%d\n", ans);
54 return 0;
55 }
56 }