蓝桥杯VIP试题 基础练习 回形取数

先记录一下这题。代码与思路并没有错，但是代码执行效率有些低，有个别数据运行超时（运行时间超过1s）。思路基本就是，下标先动，再进行该下标下的值的判断，所以用了while循环，但要注意这种方式最后一次都会越界，所以要每一次循环完后进行下标减一实现越界回位。

问题描述

　　回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。

输入格式

　　输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n个整数，表示这个矩阵。

输出格式

　　输出只有一行，共mn个数，为输入矩阵回形取数得到的结果。数之间用一个空格分隔，行末不要有多余的空格。

样例输入

3 3

1 2 3

4 5 6

7 8 9

样例输出

1 4 7 8 9 6 3 2 5

样例输入

3 2

1 2

3 4

5 6

样例输出

1 3 5 6 4 2

import java.util.*;
public class BASIC_25_8_15 {

	//回形取数函数，返回一个int型数组
	public static int[] HuiGetNum(int m, int n, int array[][]){
		int i = 0,j = 0,z = 0;
		int getResult[] = new int[m * n];
		int tag[][] = new int[m][n];//是否读取的标记,未访问统一为0，已访问统一为1
		for(int x = 0;x < m;x ++){
			for(int y = 0;y < n;y ++){
				tag[x][y] = 0;
			}
		}
		//该方法只为数组读取时限制了边界，并未考虑到运行超时错误。
		//还是分一下m或者n等于1的情况
		if(m == 1 && n != 1){
			for(int x = 0; x < m * n;x ++){
				getResult[x] = array[0][x];
			}
		}else if(m != 1 && n == 1){
			for(int x = 0;x < m * n;x ++){
				getResult[x] = array[x][0];
			}
		}else{
		
		String direction = "null";
		getResult[z] = array[i][j];
		tag[i][j] = 1;
		if(m != 1){
			i++;
		}else if(n != 1){
			j++;
		}
		//while中把j放在前面判断，就可以避免最后一次判断回来时j++溢出数组的问题
		while(i < m && j < n && array[i][j] != -1 && tag[i][j] != 1){
			//判断条件为不越界并且未被访问过
			//向下读
			while(i < m && tag[i][j] == 0 && m != 1){
				z++;
				tag[i][j] = 1;
				getResult[z] = array[i][j];
				direction = "down";
				i++;//index的++应该放在最后，作为先判断再计算的逻辑，所以每一次最后的i或j是越界的。
			}
			if(direction.equals("down")){
				i--;//撤回越界
			}
			if(!(m == 1 && n != 1)){
				j++;
			}
			//向右读
			while(j < n && tag[i][j] == 0){
				z++;
				tag[i][j] = 1;
				getResult[z] = array[i][j];
				direction = "right";
				j++;
			}
			if(direction.equals("right")){
				j--;	
			}
			if(i != 0){
				i--;
			}
			//向上读
			while(i >= 0 && tag[i][j] == 0){
				z++;
				tag[i][j] = 1;
				getResult[z] = array[i][j];
				direction = "up";
				i--;
			}
			if(direction.equals("up")){
				i++;
			}
			if(j != 0){
				j--;
			}
			//向左读
			while(j >= 0 && tag[i][j] == 0){
				z++;
				tag[i][j] = 1;
				getResult[z] = array[i][j];
				direction = "left";
				j--;
			}
			if(direction.equals("left")){
				j++;
			}
			i++;
		}
		}
		return getResult;
	}
	
	public static void main(String args[]){
		int m, n;
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		n = sc.nextInt();
		int arr[][] = new int[m][n];
		for(int i = 0;i < m;i ++){
			for(int j = 0;j < n;j ++){
				arr[i][j] = sc.nextInt();
			}
		}
		
		int Result[] = new int[m * n];
		Result = HuiGetNum(m,n,arr);
		
		//将结果输出
		for(int i = 0;i < m * n;i ++){
			System.out.print(Result[i] + " ");
		}
		
	}
}