方形拼图解决方案

Question

问题:给定一个整数n,打印数字从1到n ^2,如下所示:

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]]

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

Answer 2

虽然你的例子是用Python编写的，而这是用Java编写的，但我认为你应该能够遵循以下逻辑：

public class SquareTest {

public static void main(String[] args) {
    SquareTest squareTest = new SquareTest(4);
    System.out.println(squareTest);
}

private int squareSize;
private int[][] numberSquare;
private int currentX;
private int currentY;
private Direction currentDirection;

private enum Direction {
    LEFT_TO_RIGHT, RIGHT_TO_LEFT, TOP_TO_BOTTOM, BOTTOM_TO_TOP;
};

public SquareTest(int squareSize) {
    this.squareSize = squareSize;
    numberSquare = new int[squareSize][squareSize];
    currentY = 0;
    currentX = 0;
    currentDirection = Direction.LEFT_TO_RIGHT;
    constructSquare();
}

private void constructSquare() {
    for (int i = 0; i < squareSize * squareSize; i = i + 1) {
        numberSquare[currentY][currentX] = i + 1;
        if (Direction.LEFT_TO_RIGHT.equals(currentDirection)) {
            travelLeftToRight();
        } else if (Direction.RIGHT_TO_LEFT.equals(currentDirection)) {
            travelRightToLeft();
        } else if (Direction.TOP_TO_BOTTOM.equals(currentDirection)) {
            travelTopToBottom();
        } else {
            travelBottomToTop();
        }
    }
}

private void travelLeftToRight() {
    if (currentX + 1 == squareSize || numberSquare[currentY][currentX + 1] != 0) {
        currentY = currentY + 1;
        currentDirection = Direction.TOP_TO_BOTTOM;
    } else {
        currentX = currentX + 1;
    }
}

private void travelRightToLeft() {
    if (currentX - 1 < 0 || numberSquare[currentY][currentX - 1] != 0) {
        currentY = currentY - 1;
        currentDirection = Direction.BOTTOM_TO_TOP;
    } else {
        currentX = currentX - 1;
    }
}

private void travelTopToBottom() {
    if (currentY + 1 == squareSize || numberSquare[currentY + 1][currentX] != 0) {
        currentX = currentX - 1;
        currentDirection = Direction.RIGHT_TO_LEFT;
    } else {
        currentY = currentY + 1;
    }
}

private void travelBottomToTop() {
    if (currentY - 1 < 0 || numberSquare[currentY - 1][currentX] != 0) {
        currentX = currentX + 1;
        currentDirection = Direction.LEFT_TO_RIGHT;
    } else {
        currentY = currentY - 1;
    }
}

@Override
public String toString() {
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < squareSize; i = i + 1) {
        for (int j = 0; j < squareSize; j = j + 1) {
            builder.append(numberSquare[i][j]);
            builder.append(" ");
        }
        builder.append("\n");
    }

    return builder.toString();
}
}