蓝桥杯基础练习回形取数

朱雀 2022-06-02 08:47 231阅读 0赞

![这里写图片描述][SouthEast]

\*递归的层数太多，不能符合蓝桥杯的要求，故使用循环。

import java.util.Scanner;
    
    public class Main{ 
    
        /** * 判断该方向上是否可以取数 * @param m 数组行数 * @param n 数组列数 * @param dire 取数方向 * @param x 取数当前行数 * @param y 取数当前列数 * @param flags 取数标记 * @return true表示该方向上可以取数，false则反之 */
        public static boolean judge(int m,int n,int dire,int x,int y,boolean[][] flags){
            switch(dire) {
            case 0:return m > x + 1 && !flags[x + 1][y];
            case 1:return n > y + 1 && !flags[x][y + 1];
            case 2:return x - 1 >= 0 && !flags[x - 1][y];
            case 3:return y - 1 >= 0 && !flags[x][y - 1];
            default:return false;
            }
        }
    
        /** * 非递归回行取数 * @param arr 输入的数据 */
        public static void huixingqushu(int[][] arr)
        {
            //初始化
            int m = arr.length;
            int n = arr[0].length;
            boolean[][] flags = new boolean[m][n];
            int dire = 0;
            int x,y;
            x = y = 0;
    
            System.out.print(arr[x][y]);//先取出第一个数
            flags[x][y] = true;
            boolean resflag = true;
            while(resflag) {
                switch(dire) {
                case 0:{
                    if(judge(m,n,0,x,y,flags)) {
                        //若往下可以取数，则继续往下取
                        System.out.print(" "+arr[++x][y]);
                        flags[x][y] = true;
                    }
                    else if(judge(m,n,1,x,y,flags)) {
                        //若往右可以取数，则改变方向往右取
                        System.out.print(" "+arr[x][++y]);
                        flags[x][y] = true;
                        dire = (dire + 1) % 4;
                    }
                    else resflag = false;//下方和右方都不可取数，取数完成
                    break;
                }
                case 1:{
                    if(judge(m,n,1,x,y,flags)) {
                        //若往右可以取数，则继续往右取
                        System.out.print(" "+arr[x][++y]);
                        flags[x][y] = true;
                    }
                    else if(judge(m,n,2,x,y,flags)) {
                        //若往上可以取数，则改变方向往上取
                        System.out.print(" "+arr[--x][y]);
                        flags[x][y] = true;
                        dire = (dire + 1) % 4;
                    }
                    else resflag = false;//右方和上方都不可取数，取数完成
                    break;
                }
                case 2:{
                    if(judge(m,n,2,x,y,flags)) {
                        //若往上可以取数，则继续往上取
                        System.out.print(" "+arr[--x][y]);
                        flags[x][y] = true;
                    }
                    else if(judge(m,n,3,x,y,flags)) {
                        //若往左可以取数，则改变方向往左取
                        System.out.print(" "+arr[x][--y]);
                        flags[x][y] = true;
                        dire = (dire + 1) % 4;
                    }
                    else resflag = false;//上方和左方都不可取数，取数完成
                    break;
                }
                case 3:{
                    if(judge(m,n,3,x,y,flags)) {
                        //若往左可以取数，则继续往左取
                        System.out.print(" "+arr[x][--y]);
                        flags[x][y] = true;
                    }
                    else if(judge(m,n,0,x,y,flags)) {
                        //若往下可以取数，则改变方向往下取
                        System.out.print(" "+arr[++x][y]);
                        flags[x][y] = true;
                        dire = (dire + 1) % 4;
                    }
                    else resflag = false;//左方和下方都不可取数，取数完成
                    break;
                }
            }
            }
        }
    
        /** * 递归回行取数 * @param arr 输入的数据 * @param dest 取数方向 0:down 1:right 2:up 3: left * @param x 取数当前行数 * @param y 取数当前列数 * @param flags 取数标记 */
        public static void huixingqushu(int[][] arr,int dire,int x,int y,boolean[][] flags){
            int res = arr[x][y];
            System.out.print(" "+res);
            System.out.flush();
            flags[x][y] = true;
            int m = arr.length;
            int n = arr[0].length;
            switch(dire) {
                case 0:{
                    if(judge(m,n,0,x,y,flags)) 
                        //若往下可以取数，则继续往下取
                        huixingqushu(arr,dire,x + 1,y,flags);
                    else if(judge(m,n,1,x,y,flags))
                        //若往右可以取数，则改变方向往右取
                        huixingqushu(arr,(dire + 1) % 4,x,y + 1,flags);
                    else return;//下方和右方都不可取数，取数完成
                }
                case 1:{
                    if(judge(m,n,1,x,y,flags)) 
                        //若往右可以取数，则继续往右取
                        huixingqushu(arr,dire,x,y + 1,flags);
                    else if(judge(m,n,2,x,y,flags))
                        //若往上可以取数，则改变方向往上取
                        huixingqushu(arr,(dire + 1) % 4,x - 1,y,flags);
                    else return;//右方和上方都不可取数，取数完成
                }
                case 2:{
                    if(judge(m,n,2,x,y,flags)) 
                        //若往上可以取数，则继续往上取
                        huixingqushu(arr,dire,x - 1,y,flags);
                    else if(judge(m,n,3,x,y,flags))
                        //若往左可以取数，则改变方向往左取
                        huixingqushu(arr,(dire + 1) % 4,x,y - 1,flags);
                    else return;//上方和左方都不可取数，取数完成
                }
                case 3:{
                    if(judge(m,n,3,x,y,flags)) 
                        //若往左可以取数，则继续往左取
                        huixingqushu(arr,dire,x,y - 1,flags);
                    else if(judge(m,n,0,x,y,flags))
                        //若往下可以取数，则改变方向往下取
                        huixingqushu(arr,(dire + 1) % 4,x + 1,y,flags);
                    else return;//左方和下方都不可取数，取数完成
                }
            }
        }
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int m = scan.nextInt();
            int n = scan.nextInt();
            int[][] arr = new int[m][n];
            for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                arr[i][j] = scan.nextInt();
            scan.close();
    
            /***************递归回行取数程序段 **************/
    // System.out.print(arr[0][0]);//先取出第一个数
    // boolean[][] flags = new boolean[m][n];
    // flags[0][0] = true;
    // if(m <= 1 && n <= 1) {}//若最多只有一个数，则取数完成，不做任何操作
    // else if(m <= 1)
    // //若往下不可取数，则往右取
    // huixingqushu(arr,1,0,1,flags);
    // else
    // //否则往下取
    // huixingqushu(arr,0,1,0,flags);
            /*****************NED*********************/
    
            /***************非递归回行取数程序段 **************/
            huixingqushu(arr);
            /*****************NED*********************/
        }
    }

[SouthEast]: /images/20220602/e84871bbe105445fb138d3082fbb54a3.png