藍橋杯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] + " ");
		}
		
	}
}