学步园

题目：给定一个数N（N = M^2 - 1）输出0、1、……、N的螺旋序列，其中M为正整数。

例如M为5时，输出如下序列。

0      1     2     3     4
15   16   17   18   5
14   23   24   19   6
13   22   21   20   7
12   11   10   9     8

解法：考虑设定一个(M + 2)^2大小的二维数组，边界部分赋值为-1，便于打印的时候识别边界，中间部分螺旋赋值。代码如下。

#include <iostream>

#define MAX_BASE 100

using namespace std;

void fill_and_print(int _base)
{
	int total = _base * _base;
	int tofill[MAX_BASE + 2][MAX_BASE + 2];
	memset(tofill, 0, sizeof(int) * (MAX_BASE + 2) * (MAX_BASE + 2));
	tofill[0][0] = tofill[0][_base + 1] = tofill[_base + 1][0] = tofill[_base + 1][_base + 1] = -1;
	for(int countBase = 0; countBase < _base; ++countBase)
	{
		tofill[0][countBase + 1] = -1;
		tofill[_base + 1][countBase + 1] = -1;
		tofill[countBase + 1][0] = -1;
		tofill[countBase + 1][_base + 1] = -1;
	}
	int direction = 0; // 0 means right, 1 means down, 2 means left, 3 means up
	int initColumn = 1;
	int initRow = 2;
	tofill[1][1] = -1;
	for(int count = 1; count < total; ++count)
	{
		switch(direction)
		{
			case 0:
				if(tofill[initColumn][initRow + 1] != 0)
				{
					tofill[initColumn++][initRow] = count;
					direction = 1;
				}
				else
				{
					tofill[initColumn][initRow++] = count;
				}
				break;
			case 1:
				if(tofill[initColumn + 1][initRow] != 0)
				{
					tofill[initColumn][initRow--] = count;
					direction = 2;
				}
				else
				{
					tofill[initColumn++][initRow] = count;
				}
				break;
			case 2:
				if(tofill[initColumn][initRow - 1] != 0)
				{
					tofill[initColumn--][initRow] = count;
					direction = 3;
				}
				else
				{
					tofill[initColumn][initRow--] = count;
				}
				break;
			case 3:
				if(tofill[initColumn - 1][initRow] != 0)
				{
					tofill[initColumn][initRow++] = count;
					direction = 0;
				}
				else
				{
					tofill[initColumn--][initRow] = count;
				}
				break;
			default:
				break;
		}
	}
	tofill[1][1] = 0;
	// print array
	for(int countColumn = 1, countRow = 1; (countColumn < _base + 1) && (countRow < _base + 2);)
	{
		if(tofill[countColumn][countRow] == -1)
		{
			cout<<endl;
			++countColumn;
			countRow = 1;
			continue;
		}
		else
		{
			cout<<tofill[countColumn][countRow++]<<"\t";
		}
	}
}

int main()
{
	for(int testNumber = 1; testNumber < 11; ++testNumber)
	{
		cout<<"Array while base number equals "<<testNumber<<":"<<endl;
		fill_and_print(testNumber);
		cout<<endl;
	}
	return 0;
}

测试数据为M从1到10，输出结果如下。

Array while base number equals 1:
0

Array while base number equals 2:
0       1
3       2

Array while base number equals 3:
0       1       2
7       8       3
6       5       4

Array while base number equals 4:
0       1       2       3
11      12      13      4
10      15      14      5
9       8       7       6

Array while base number equals 5:
0       1       2       3       4
15      16      17      18      5
14      23      24      19      6
13      22      21      20      7
12      11      10      9       8

Array while base number equals 6:
0       1       2       3       4       5
19      20      21      22      23      6
18      31      32      33      24      7
17      30      35      34      25      8
16      29      28      27      26      9
15      14      13      12      11      10

Array while base number equals 7:
0       1       2       3       4       5       6
23      24      25      26      27      28      7
22      39      40      41      42      29      8
21      38      47      48      43      30      9
20      37      46      45      44      31      10
19      36      35      34      33      32      11
18      17      16      15      14      13      12

Array while base number equals 8:
0       1       2       3       4       5       6       7
27      28      29      30      31      32      33      8
26      47      48      49      50      51      34      9
25      46      59      60      61      52      35      10
24      45      58      63      62      53      36      11
23      44      57      56      55      54      37      12
22      43      42      41      40      39      38      13
21      20      19      18      17      16      15      14

Array while base number equals 9:
0       1       2       3       4       5       6       7       8
31      32      33      34      35      36      37      38      9
30      55      56      57      58      59      60      39      10
29      54      71      72      73      74      61      40      11
28      53      70      79      80      75      62      41      12
27      52      69      78      77      76      63      42      13
26      51      68      67      66      65      64      43      14
25      50      49      48      47      46      45      44      15
24      23      22      21      20      19      18      17      16

Array while base number equals 10:
0       1       2       3       4       5       6       7       8       9

35      36      37      38      39      40      41      42      43      10

34      63      64      65      66      67      68      69      44      11

33      62      83      84      85      86      87      70      45      12

32      61      82      95      96      97      88      71      46      13

31      60      81      94      99      98      89      72      47      14

30      59      80      93      92      91      90      73      48      15

29      58      79      78      77      76      75      74      49      16

28      57      56      55      54      53      52      51      50      17

27      26      25      24      23      22      21      20      19      18