题意:贪吃蛇,要求长度奇数的蛇转弯次数为正奇数,长度偶数转弯次数为正偶数,且组成矩形。(北大出的题咋都和矩形相关!!!)
分析:构造找规律,想到就简单了。可以构造 宽:(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 7 7 7 7 7
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 9 9 9 9 9 9 9
#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\n1 1\n", "1 3\n1 1\n1 2 1 3\n", "2 3\n1 2\n1 3 2 3\n1 1 2 1 2 2\n", "2 5\n1 4\n1 5 2 5\n1 1 2 1 2 2\n1 2 1 3 2 3 2 4\n", "3 4\n1 4 1 5\n2 4 2 5 3 5\n2 2 2 3 3 3 3 2\n3 1 2 1 1 1 1 2 1 3\n"}; 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\n", x, y); printf ("%s", ans[4]); DFS (4, 6, 6, n); } } return 0; }