codeforces 441C. Valera and Tubes 解题报告

题目链接：http://codeforces.com/problemset/problem/441/C

题目意思：将n * m 的矩阵分成 k 堆。每堆是由一些坐标点（x, y）组成的。每堆里面至少由 >= 2 个坐标点组成，这些坐标点还需要满足： |x_i - x_i + 1| + |y_i - y_i + 1| = 1 。这个等式表示遍历堆里面的坐标好像蛇形那样走，也就是坐标点与坐标点之间需要相邻！还有一个条件就是，每个坐标点只能用一次。

做了一整天= =。改了一个问题，另一个问题又出现了。终于被一个问题攻陷了= =。

整体思路就是 k - 1堆中，每堆由两个坐标组成，剩下的那一堆，由剩下未用的坐标构成。由于我做的时候是一竖竖地做的（假设 3 * 5的矩阵，1 1 1 2 2 1 2 2...），所以有个问题就是剩下的那堆，从第一行开始走的时候，是从左到右走还是从右到左走？我错误的代码中，判断不了对于分完k-1堆之后，箭头是如何走的！我是通过k-1堆之后被覆盖的总行数的奇偶数来判断的：奇数：从左至右，偶数：从右至左。但是对于行数为奇数来说，就不行了。以下这两种情况足以证实。

5 9 20

（被覆盖的总行数为奇数，但正确走法应该是从右至左）

2 2 1

（与推测相同）

先贴下我错的代码（读者可直接忽略），一场噩梦= =

（test 24 错了，说堆中有些tube 不符合条件）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn = 300 + 5;
 8 int vis[maxn][maxn];
 9 
10 int main()
11 {
12     int n, m, k;
13     while (scanf("%d%d%d", &n, &m, &k) != EOF)
14     {
15         memset(vis, 0, sizeof(vis));
16         int row = 1, y = 1;
17         int cnt, tmp, f = 0, sum = 0;
18         for (cnt = 1; cnt <= k-1; )
19         {
20             if (y+1 > m)
21                 break;
22             printf("2 %d %d %d %d
", row, y, row, y+1);
23             vis[row][y] = vis[row][y+1] = 1;
24             sum += 2;
25             row++;
26             cnt++;
27             if (!(row % n) && cnt+1 <= k-1)
28             {
29                 printf("2 %d %d %d %d
", row, y, row, y+1);
30                 vis[row][y] = vis[row][y+1] = 1;
31                 sum += 2;
32                 y += 2;
33                 row = 1;
34                 f = 1;
35                 cnt++;
36             }
37         }
38         int col = m;
39         for (int row = 1; row+1 <= n && cnt <= k-1; row += 2, cnt++)
40         {
41             printf("2 %d %d %d %d
", row, col, row+1, col);
42             vis[row][col] = vis[row+1][col] = 1;
43             sum += 2;
44         }
45         tmp = (!f ? row-1 : n);
46       //  printf("tmp = %d
", tmp);
47         if ((n*m)-sum)
48         {
49             printf("%d ", n*m-sum);
50             int start = (tmp&1 ? 1 : 0);  // 奇数顺着来走
51             for (int row = 1; row <= n; row++)
52             {
53                 if (start)
54                 {
55                     for (int col = 1; col <= m; col++)
56                     {
57                         if (!vis[row][col])
58                             printf("%d %d ", row, col);
59                     }
60                 }
61                 else
62                 {
63                     for (int col = m; col >= 1; col--)
64                     {
65                         if (!vis[row][col])
66                             printf("%d %d ", row, col);
67                     }
68                 }
69                 start ^= 1;
70             }
71         }
72         printf("
");
73     }
74     return 0;
75 }

AC代码（真是简单就为美啊～～～）

规规矩矩，一行行顺着来做

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 int n, m, k;
 8 
 9 void next(int &x, int &y)
10 {
11     if (y == 1)
12     {
13         if (x & 1)
14             y++;
15         else
16             x++;
17     }
18     else if (y == m)
19     {
20         if (x & 1)
21             x++;
22         else
23             y--;
24     }
25     else if (x & 1)
26         y++;
27     else
28         y--;
29 }
30 
31 int main()
32 {
33     while (scanf("%d%d%d", &n, &m, &k) != EOF)
34     {
35         int x = 1, y = 1;
36         int cnt = k;
37         while (cnt > 1)
38         {
39             printf("2");
40             printf(" %d %d", x, y);
41             next(x, y);
42             printf(" %d %d
", x, y);
43             next(x, y);
44             cnt--;
45         }
46         printf("%d", n*m-2*(k-1));
47         while (x >= 1 && x <= n && y >= 1 && y <= m)
48         {
49             printf(" %d %d", x, y);
50             next(x, y);
51         }
52         puts("");
53     }
54     return 0;
55 }