試題 基礎練習 回形取數（Java）

資源限制

時間限制：1.0s 內存限制：512.0MB

問題描述

　　回形取數就是沿矩陣的邊取數，若當前方向上無數可取或已經取過，則左轉90度。一開始位于矩陣左上角，方向向下。

輸入格式

　　輸入第一行是兩個不超過200的正整數m, n，表示矩陣的行和列。接下來m行每行n個整數，表示這個矩陣。

輸出格式

　　輸出只有一行，共m*n個數，為輸入矩陣回形取數得到的結果。數之間用一個空格分隔，行末不要有多余的空格。

樣例輸入

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.Scanner;
import java.util.Vector;
?
public class Main {
    
    static int vis[][];//標記這個位置有沒有走過
    static int m,n;//輸入的矩陣的行數、列數
?
    static class node{//內部類，相當于c++和c的結構體數組，不過這里注意要在前面加static
        int a,b;
    }
?
    static boolean check(int l,int r)//判斷元素(l,r)在不在矩陣里
    {
        if(l<1||l>m||r<1||r>n)
            return false;
        return true;
    }
    
    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in); 
        m = sc.nextInt(); 
        n = sc.nextInt(); 
        
        int[][] a = new int[m+1][n+1]; //實例化一個二維矩陣a
        vis=new int[300][300];//對vis進行初始化，一定要這一句，不然vis并沒有分配空間
        for (int i = 1; i <=m; i++) { 
            for (int j = 1; j <=n; j++) { 
                a[i][j] = sc.nextInt(); //輸入題目給的矩陣
            } 
        } 
        node[] d=new node[5];//初始化數組d
        for(int i=0;i<5;i++){//一定要加入這一句
            d[i]=new node();//再分別對每一個d[i]創建對象
        }
        //d[0]=new node();
        int forward=0;
        d[0].a=1;d[0].b=0;//d[0]代表向下走，x+1，y不變
        d[1].a=0;d[1].b=1;//d[1]代表向右走，x不變，y+1
        d[2].a=-1;d[2].b=0;//d[2]代表向上走，x-1，y不變
        d[3].a=0;d[3].b=-1;//d[3]代表向左走，x不變，y-1
        int cnt=n*m;//cnt用來計數
        int x=1,y=1;//從(1,1)開始往下走
        Vector st=new Vector();//用來存數字
        while(cnt>0)
        {
            if(check(x,y)&&vis[x][y]==0)//如果這個點在矩陣里并且沒有訪問過的話，代表它是合法的
            {
                cnt--;
                st.addElement(new Integer(a[x][y]));//我們就把它放到vector里面
                vis[x][y]=1;//這個點就標記為1，代表不可訪問
            }
            if(cnt==0)//代表所有點都已經壓入vector里了
                break;
            while(!(check(x+d[forward].a, y+d[forward].b) && vis[x+d[forward].a][y+d[forward].b] == 0))//當這個點的下一個狀態不在矩陣里，并且下一個點被訪問過的話
            {//就代表我們應該拐彎啦
                forward = (forward+1)%4;//那么我們就把forward+1
            }
            x=x+d[forward].a;//再把坐標更新
            y=y+d[forward].b;
        }
        System.out.print(st.get(0));//這里就是輸出啦
        int len=st.size();
        for(int i=1;i<len;i++)
        {
            System.out.print(" "+st.get(i));
        }
        
    } 
}

總結

首先是對于方向

從這道題我們可以看出來其實就是一條直線上的全部點，那么我們可以發現一個規律，一條直線上的點它的x和y是有某種規律的，我們可以寫成上面d[0]等那樣，然后每次分別代表向下，向右，向上，向左的方向

其次是內部類

因為之前一直是用的C++寫題，現在突然轉到java其實是不太熟練的，所以一時不知道結構體在java要怎么寫。

然后去咨詢了一下別人，知道了內部類這個東西，去網上百度了一下，最后得到結論，可以在Main類里面寫，然后在前面加一個static就好了。但是用的時候要先確定大小，node[] d=new node[5];//初始化數組d。然后還要分別對每一個元素創建對象，我感覺時間復雜度變高了。

然后就是Vector了

初始化

Vector st=new Vector();//用來存數字

容器的大小

st.size();//代表它存了多少數
//不能用st.capicty()，這個返回的是st的容量，而不是里面存了多少數

往里面添加元素

st.add();//或者st.addElement()

得到第i個元素

st.get(i);//這個返回的是第i個元素