题意：贪吃蛇，要求长度奇数的蛇转弯次数为正奇数，长度偶数转弯次数为正偶数，且组成矩形。(北大出的题咋都和矩形相关！！！)
分析：构造找规律，想到就简单了。可以构造 宽：(n + 1) / 2， 长(n + 1) * n / 2 / (n + 1) / 2的矩形;
n = 5
1 2 4 4 5
3 2 4 4 5
3 3 5 5 5
n = 7
1 2 4 4 5 6 6
3 2 4 4 5 6 6
3 3 5 5 5 7 6
7 7 7 7 7 7 6
n = 8
1 2 4 4 5 6 6 8 8
3 2 4 4 5 6 6 8 8
3 3 5 5 5 7 6 8 8
7 7 7 7 7 7 6 8 8
n = 9
1 2 4 4 5 6 6 8 8
3 2 4 4 5 6 6 8 8
3 3 5 5 5 7 6 8 8
7 7 7 7 7 7 6 9 8
9 9 9 9 9 9 9 9 8
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
Point () {}
Point (int x, int y) : x (x), y (y) {}
};
char ans[5][100] = { "1 1
1 1
", "1 3
1 1
1 2 1 3
", "2 3
1 2
1 3 2 3
1 1 2 1 2 2
",
"2 5
1 4
1 5 2 5
1 1 2 1 2 2
1 2 1 3 2 3 2 4
",
"3 4
1 4 1 5
2 4 2 5 3 5
2 2 2 3 3 3 3 2
3 1 2 1 1 1 1 2 1 3
"};
void print(vector<Point> &vec) {
printf ("%d %d", vec[0].x, vec[0].y);
for (int i=1; i<vec.size (); ++i) {
printf (" %d %d", vec[i].x, vec[i].y);
}
puts ("");
vec.clear ();
}
void DFS(int r, int c, int d, int n) {
if (d > n) return ;
vector<Point> vec;
if (d == n) {
for (int i=1; i<r; ++i) vec.push_back (Point (i, c));
for (int i=r-1; i>=1; --i) vec.push_back (Point (i, c + 1));
print (vec);
return ;
}
else {
for (int i=r-2; i>=1; --i) vec.push_back (Point (i, c));
for (int i=1; i<=r; ++i) vec.push_back (Point (i, c + 1));
print (vec);
for (int i=1; i<=c; ++i) vec.push_back (Point (r, i));
vec.push_back (Point (r-1, c));
print (vec);
}
DFS (r + 1, c + 2, d + 2, n);
}
int main(void) {
int n;
while (scanf ("%d", &n) == 1) {
if (n < 5) {
printf ("%s", ans[n-1]);
}
else {
int x = (n + 1) / 2;
int y = (n + 1) * n / 2 / x;
printf ("%d %d
", x, y);
printf ("%s", ans[4]);
DFS (4, 6, 6, n);
}
}
return 0;
}