南阳OJ-No.33-蛇形填数

[TOC]

南阳OJ-No.33

时间限制3000ms,空间限制65535KB,难度3

描述

在nn方陈里填入1,2,…,nn,要求填成蛇形。例如n=4时方阵为:

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

输入

直接输入方陈的维数,即n的值。(n<=100)

输出

输出结果是蛇形方陈。

样例输入

3

样例输出

7 8 1
6 9 2
5 4 3


思路:4 连通问题
n=1,特殊情况
n>2,
我先画出了n=2,3,4,5,6的蛇形数组进行观察,数组构建过程是从右上角的数字1开始,然后按照顺时针方向依次构建。方阵中每个格子相邻的都有四个格子。观察构建顺序,数字存放顺序为顺时针方向,即下、左、上、右,进行循环判断填充,注意判断数组下标不越界


JAVA

时间83,内存1475

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.Scanner;

public class Main {
public static Scanner cin = new Scanner(System.in);
public static int N = cin.nextInt(), x = 0, y = N-1, count = 1;
public static int[][] num = new int[N][N];

static {
for (int x=0; x<N; x++) {
for (int y=0; y<N; y++) {
num[x][y] = 0;
}
}

num[x][y] = 1;
}

public static void print(int[][] num) {
for (int x=0; x<N; x++) {
for (int y=0; y<N; y++) {
System.out.print(num[x][y] + " ");
}
System.out.println();
}
}

public static void main(String[] args) throws Exception {
while(count < N*N) {
while(x<N-1 && num[x+1][y]==0)
num[++x][y] = ++count;

while(y>0 && num[x][y-1]==0)
num[x][--y] = ++count;

while(x>0 && num[x-1][y]==0)
num[--x][y] = ++count;

while(y<N-1 && num[x][y+1]==0)
num[x][++y] = ++count;
}
print(num);
}
}

这个是在南阳OJ中扒出来的以为大神,不懂啊(⊙﹏⊙)
时间36,内存676

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.Scanner;

public class Main{
public static void main(String[] args) {
int i,j,h = 0;
short num = 1;
Scanner scanner = new Scanner(System.in);
short n = scanner.nextShort();
short[][] array = new short[n][n];
int hmax = (n+1)>>1;
for ( h = 0; h <= hmax; h++) {
if (h==hmax&&n%2!=0) {
array[n>>1][n>>1] = num;
}else {
for ( i =h; i < n-1-h; i++) {
array[i][n-1-h]=num++;
}
for ( i = n-1-h; i >h ; i--) {
array[n-1-h][i]=num++;
}
for ( i = n-1-h; i >h ; i--) {
array[i][h]=num++;
}
for ( i = h; i < n-1-h; i++) {
array[h][i] = num++;
}
}
}
StringBuffer sb = new StringBuffer();
for ( i = 0; i < array.length; i++) {
for ( j = 0; j < array[i].length; j++) {
sb.append(array[i][j]).append(" ");
}
sb.append("\n");
}
System.out.print(sb);
}
}

C++

时间4,内存240

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
using namespace std;

int main()
{
int N, x, y, count;

cin >> N;
x = 0;
y = N-1;
count = 1;

int num[N][N];

for (int x=0; x<N; x++) {
for (int y=0; y<N; y++) {
num[x][y] = 0;
}
}

num[x][y] = 1;

while(count < N*N) {
while(x<N-1 && num[x+1][y]==0)
num[++x][y] = ++count;

while(y>0 && num[x][y-1]==0)
num[x][--y] = ++count;

while(x>0 && num[x-1][y]==0)
num[--x][y] = ++count;

while(y<N-1 && num[x][y+1]==0)
num[x][++y] = ++count;
}

for (int x=0; x<N; x++) {
for (int y=0; y<N; y++) {
cout << num[x][y] << " ";
}
cout << endl;
}

return 0;
}
文章作者: HibisciDai
文章链接: http://hibiscidai.com/2017/02/15/2017-02-15-南阳OJ-No.33-蛇形填数/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HibisciDai