[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

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

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

#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;
}