algorithm - 方形拼图解

Question

问题:给定一个整数 n，打印从 1 到 n² 的数字，如下所示:

n = 4

结果是:

01 02 03 04
12 13 14 05
11 16 15 06
10 09 08 07

你如何解决它(除了下面链接中提供的解决方案)？

http://www.programmersheaven.com/mb/CandCPP/81986/81986/problem-in-making-ap-c++-program/?S=B20000

我正在看另一个方向。到目前为止，我正在尝试弄清楚我是否可以获得我必须填写的职位的有序列表。

这就是我正在研究的内容:有没有一种方法可以获取“fdisp”以便以这种方式解决问题，而不是在矩阵中“行走”？

matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
n = len(matrix)

# final disposition wrote by hand: how to get it for arbitrary n?
fdisp = [(0,0), (0,1), (0,2), (0,3), (1,3), (2,3), (3,3), (3,2),
         (3,1), (3,0), (2,0), (1,0), (1,1), (1,2), (2,2), (2,1)]

for val,i in enumerate(fdisp):
    matrix[i[0]][i[1]] = val + 1

def show_matrix(matrix, n):
    for i,l in enumerate(matrix):
        for j in range(n):
            print "%d\t" % matrix[i][j],
        print

show_matrix(matrix, n)

Answer 1

这是一种不同的方法。它依赖于发现您所做的运动在以下之间循环:右，下，左，上，右，...。此外，您移动的次数为:向右 3 次，向下 3 次，向左 3 次，向上 2 次，向右 2 次, 1 下, 1 左。因此，事不宜迟，我将使用 Python 编写代码。

首先，我将使用一些 itertools 和一些 numpy:

from itertools import chain, cycle, imap, izip, repeat
from numpy import array

方向在以下之间循环:右、下、左、上、右……:

directions = cycle(array(v) for v in ((0,1),(1,0),(0,-1),(-1,0)))

(我在这里使用了 numpy 的数组，所以我可以很容易地将方向添加在一起。元组添加得不好。)

接下来我移动的次数从n-1倒数到1，每个数字重复两次，第一个数字重复三次:

countdown = chain((n-1,), *imap(repeat, range(n-1,0,-1), repeat(2)))

现在我的方向序列可以通过在倒计时中按配对数字重复每个连续方向来创建:

dirseq = chain(*imap(repeat, directions, countdown))

为了得到我的索引序列，我可以只对这个序列求和，但是(AFAIK)Python 没有提供这样的方法，所以让我们快速地把一个放在一起:

def sumseq(seq, start=0):
  v = start
  yield v
  for s in seq:
    v += s
    yield v

现在要生成原始数组，我可以执行以下操作:

a = array(((0,)*n,)*n) # n-by-n array of zeroes
for i, v in enumerate(sumseq(dirseq, array((0,0)))):
  a[v[0], v[1]] = i+1
print a

对于 n = 4，给出:

[[ 1  2  3  4]
 [12 13 14  5]
 [11 16 15  6]
 [10  9  8  7]]

并且，对于 n = 5，给出:

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

这种方法可以推广到矩形网格；我把它留给读者作为练习 ;)