問題の説明は次のとおりです。
2次元配列が与えられた場合、たとえば出力を出力します
4行6列の場合、出力は次のようになります。
1 2 3 4 5 6
16 17 18 19 20 7
15 24 23 22 21 8
14 13 12 11 10 9
私はそれが正方形の中の正方形のように見えることを試みました、しかし私がこの問題を試みたとき、私はたくさんのwhileとifループを入れましたが、正確な答えは得られませんでした。行と列がそれを処理する方法を増やす場合はどうなりますか？
これは宿題ではありません。私は複雑な構造を解くことを学んでいたので、いくつかのガイダンスによってそれを理解する必要があります。
四角いスパイラルです。
あなたはここでそれについて読むことができます：http：//metacpan.org/pod/Math :: PlanePath ::
SquareSpiral
数式の説明があります。
これが私が持ってきたものです。
変数名は逆さま/逆さまかもしれません、強化、削除、変更することがたくさんありますが、それは楽しいゲームでした。
public class Test {
public static void main(String[] args) {
int x = 2;
int y = 2;
int idx = 1;
int[][] array = new int[x][y];
int yUpIdx = y-1;
int yDownIdx = 0;
int xLeftIdx = 0;
int xRightIdx = x-1;
while (idx < x*y) {
for (int i = xLeftIdx; idx <= x*y && i <= xRightIdx; i++) {
array[i][yDownIdx] = idx++;
}
yDownIdx++;
for (int j = yDownIdx; idx <= x*y && j <= yUpIdx; j++) {
array[xRightIdx][j] = idx++;
}
xRightIdx--;
for (int i = xRightIdx; idx <= x*y && i>=xLeftIdx ; i--) {
array[i][yUpIdx] = idx++;
}
yUpIdx--;
for (int j = yUpIdx; idx <= x*y && j>=yDownIdx ; j--) {
array[xLeftIdx][j] = idx++;
}
xLeftIdx++;
}
for (int j = 0; j < y; j++) {
for (int i = 0 ; i < x; i++) {
if ((array[i][j]+"").length() < 2) System.out.print(" ");
System.out.print(array[i][j]+" ");
}
System.out.println("");
}
}
同じ「らせん状に歩く」アルゴリズムを使用する別の解決策：
public class SpiralArray {
private int[][] cells;
private int rows;
private int cols;
private enum Direction {
LEFT,
DOWN,
RIGHT,
UP
}
public SpiralArray(int cols, int rows) {
this.cols = cols;
this.rows = rows;
cells = new int[cols][rows];
int count = 0;
Direction direction = Direction.RIGHT;
int x=0, y=0;
while (count++ < cols*rows) {
cells[x][y]=count;
switch (direction) {
case LEFT:
if ((--x<0) || (cells[x][y]>0)) {
y--;
x++;
direction = Direction.UP;
}
break;
case RIGHT:
if ((++x==cols) || (cells[x][y]>0)) {
y++;
x--;
direction = Direction.DOWN;
}
break;
case UP:
if ((--y<0) || (cells[x][y]>0)) {
x++;
y++;
direction = Direction.RIGHT;
}
break;
case DOWN:
if ((++y==rows) || (cells[x][y]>0)) {
x--;
y--;
direction = Direction.LEFT;
}
break;
}
}
}
int get(int i, int j) {
return cells[i][j];
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
for (int y=0; y<rows; y++) {
for (int x=0; x<cols; x++) {
sb.append(cells[x][y]).append("\t");
}
sb.append("\n");
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(new SpiralArray(6, 4));
}
}
このアイデアがあなたを始めるのに役立つことを願っています：
void solve2DArray(bool[][] 2DArray, int i, int j, int numMoves)
{
2DArray[i][j] = true; // Mark current position as visited
// Perhaps a print statement here
if(right is not visited and can move right)
// move right
else if(down is not visited and can move down)
// move down
// ...
// ...
}
おそらく、ゼロに初期化されたNxM整数配列を作成します。1、0,0、およびに設定nextNumberします。が配列の外側にあることを確認し、セルのゼロを確認します。OKでセルがゼロの場合は、そこに格納して増分します。次に、に基づいて、増分します。positiondirectionleft-to-rightpositionpositionpositionnextNumbernextNumberdirectionposition
のセルpositionがゼロ以外の場合、またはのインデックスの1つpositionが<0または> =配列サイズの場合は、方向を変更する必要があります。positionまず、既存の方向を使用して1ずつバックアップします。direction次に、現在の値から90度の新しい値を選択し、インクリメントpositionして、再試行します。
完了した方向に進むことができない場合は、配列を印刷します。
（おそらく、上記で誤って処理したいくつかの境界条件ですが、これは1つの基本的なアルゴリズムです。）
position（ヒント：に基づいてインクリメント/デクリメントするサブルーチンを作成しますdirection。）
アレイ内を移動するワームを作成できると思います。
public class Worm {
public static void main(String[] args) {
int[][] outArray = runWormRun(6, 4);
printArray(outArray);
}
private static void printArray(int[][] outArray) {
for (int j = 0; j < outArray[0].length; j++) {
for (int i = 0; i < outArray.length; i++) {
System.out.print(String.format("%02d ", outArray[i][j]));
}
System.out.println();
}
}
private static int[][] runWormRun(int w, int h) {
int[][] output = new int[w][h];
int counter = 0;
int wormX = 0, wormY = 0;
int minX = 0, maxX = w - 1, minY = 0, maxY = h - 1;
int dirX = 0, dirY = 1;
while (counter < w * h) {
output[wormX][wormY] = ++counter;
// let the worm walk
wormX += dirX;
wormY += dirY;
// update direction of worm for next iteration
if ((dirX != 0 && dirY != 1) && wormX == minX && wormY == minY) { // upper left border (and not yet rotated correctly
dirX = 0; dirY = 1; minY++;
}
if ((dirX != -1 && dirY != 0) && wormX == maxX && wormY == minY) { // upper right border
dirX = -1; dirY = 0; maxX--;
}
if ((dirX != 0 && dirY != -1) && wormX == maxX && wormY == maxY) { // lower right border
dirX = 0; dirY = -1; maxY--;
}
if ((dirX != 1 && dirY != 0) && wormX == minX && wormY == maxY) { // lower left border
dirX = 1; dirY = 0; minX++;
}
}
return output;
}
}
そして、はい、私のワームは反対方向に移動します。なぜなら、私も少し考えて、私が何をしていたかを理解してほしいからです。これは宿題だと思うので。（それが本当なら、質問に「宿題」タグを追加することを検討してください。）
編集：おっと、正確には、それが何をすべきかではありません。今は時間がないので、夕方にそれを調べます。
別のテイク：
public class Test {
enum Dir {
R(0,1), L(0,-1), D(1,0), U(-1,0);
public final int rowd, cold;
private Dir(int rowd, int cold) { this.rowd = rowd; this.cold = cold; }
public Dir next() { return values()[(ordinal()+1) % values().length]; }
}
static final int rows = 4, cols = 6;
static final int[][] grid = new int[rows][cols];
static int row, col = -1, step;
public static void main(String[] args) {
Dir dir = Dir.R;
moving: while (true) {
for (int i = 0; i < Dir.values().length; i++, dir = dir.next())
if (move(dir)) continue moving;
break;
}
for (int[] row : grid) System.out.println(Arrays.toString(row));
}
static boolean move(Dir dir) {
final int newRow = row+dir.rowd, newCol = col+dir.cold;
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols
&& grid[newRow][newCol] == 0)
{
row = newRow; col = newCol; grid[row][col] = ++step; return true;
}
return false;
}
}
スクエアスパイラル
これは、最適に実行される単一の関数のコンパクトなソリューションです（配列内の各場所に1回だけアクセスします）。
static int anMoveXDir[] = { 1, 0, -1, 0 };
static int anMoveYDir[] = { 0, 1, 0, -1 };
static void DoSpiral(int *panGrid, int nWidth, int nHeight)
{
int nSideSel, nSideIdx, nMoveDir, nXPosn, nYPosn, nCounter;
int anSideLen[2];
anSideLen[0] = nWidth;
anSideLen[1] = nHeight - 1;
nMoveDir = 0; /* start off at (0, 0) in array, */
nXPosn = 0; /* facing east, and count from 1 */
nYPosn = 0;
nCounter = 1;
for (nSideSel = 0; anSideLen[nSideSel & 1]; anSideLen[nSideSel++ & 1]--)
for (nSideIdx = anSideLen[nSideSel & 1]; nSideIdx; nSideIdx--)
{
panGrid[(nYPosn * nWidth) + nXPosn] = nCounter++;
if (nSideIdx == 1)
nMoveDir = (nMoveDir + 1) & 3;
nXPosn += anMoveXDir[nMoveDir];
nYPosn += anMoveYDir[nMoveDir];
}
}
xこのアルゴリズムは、幅と高さの長方形または正方形の配列を指定した単純なルールで機能しますy。次に、配列をウォークして正方形のスパイラルを作成するには、次の手順を使用します。
x + (y - 1) + (x - 1) + (y - 2) + (x - 2) + (y - 3) + (x - 3) + ... + 0
上記の関数は、単に上記のシーケンスに従います。アレイの左上を東に向けて開始し、ステップを歩き、右に90度回転し、ステップxを歩き、右に90度曲がり、ステップ(y - 1)を歩き(x - 1)ます。xy
以下のテストプログラムに挿入することで、上記の関数をテストできます。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define GRID_WIDTH 7
#define GRID_HEIGHT 11
void main()
{
int nXPosn, nYPosn;
int anGrid[GRID_WIDTH * GRID_HEIGHT];
int *pnValue;
DoSpiral(anGrid, GRID_WIDTH, GRID_HEIGHT);
for (pnValue = anGrid, nYPosn = 0; nYPosn < GRID_HEIGHT; nYPosn++, printf("\n"))
for (nXPosn = 0; nXPosn < GRID_WIDTH; printf("%4i", *pnValue++), nXPosn++);
}
出力は次のようになります（上記のプログラムに示されている7x11グリッドの場合）。
1 2 3 4 5 6 7
32 33 34 35 36 37 8
31 56 57 58 59 38 9
30 55 72 73 60 39 10
29 54 71 74 61 40 11
28 53 70 75 62 41 12
27 52 69 76 63 42 13
26 51 68 77 64 43 14
25 50 67 66 65 44 15
24 49 48 47 46 45 16
23 22 21 20 19 18 17