阿里笔试题破解八卦阵问题

题目如下：

八卦阵相传是诸葛亮创设的一种战斗队形和***，由八种阵势组成。为了方便，采用矩阵描述一个八卦阵，它由八个单阵组成，，每个单阵由多个兵力区域组成一种阵势，如图所示，其中数字为一个兵力区域的士兵个数。假设单阵与单阵之间兵力区域不会相邻，且单阵中兵力区域至少存在一个兵力相邻区域（注：相邻是指再其↖、正上、↗、正右、↘、正下、↙、正左八个方位与其相邻），请用最快的速度计算出八个单阵中的兵力（士兵个数）的最大值和最小值。

使用广度优先的算法BFS。洪水充填法。代码如下：

import java.util.Scanner;

public class Eighttactics {    //八卦阵
    //模拟队列
    //用两个二维的数组
    public  static int ans = 0;
    public static int maxnum = 0;
    public static int minNum = 0x3f3f3f3f;
    public static int sum;
    public static int []qx = new int[1000];
    public static int []qy = new int[1000];

    public static int check(int x ,int y ,int r,int [][] grid,int m,int n){
        if(x >= 0 && x<m && y >= 0 && y< n && grid[x][y] > 0)
        {
            sum += grid[x][y];
            grid[x][y] = 0;  //每个海水侵蚀的地方就要变为水 0
            // 队列入队
            qx[r] = x;
            qy[r] = y;
            ++r;   //队尾加一
        }
        return r;
    }

    public static void floodfill(int x,int y,int[][] grid,int m,int n){
        int h = 0;
        int r = 1;
        qx[h] = x;
        qy[h] = y;
        sum += grid[x][y];
        grid[x][y] = 0;
        while(h<r){         //[h,r)左开右闭
            r = check(qx[h]-1,qy[h],r,grid,m,n);
            r = check(qx[h]+1,qy[h],r,grid,m,n);
            r = check(qx[h],qy[h]-1,r,grid,m,n);
            r = check(qx[h],qy[h]+1,r,grid,m,n);
            r = check(qx[h]-1,qy[h]+1,r,grid,m,n);
            r = check(qx[h]+1,qy[h]+1,r,grid,m,n);
            r = check(qx[h]+1,qy[h]-1,r,grid,m,n);
            r = check(qx[h]-1,qy[h]+1,r,grid,m,n);
            h++;
        }
    }
    public int maxAndMin(int [][] grid) {       //非递归的方式
        if(grid.length == 0 || grid[0].length == 0)
            return 0;
        int m = grid.length;
        int n = grid[0].length;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(grid[i][j] > 0)
                {
                    sum = 0;
                    floodfill(i,j,grid,m,n);    //floodfill(0,0,grid);遍历每一个格子
                    if(maxnum < sum){
                        maxnum = sum;
                    }
                    if(minNum > sum)
                    {
                        minNum = sum;
                    }
                    ans++;       //返回孤岛或者八卦阵的个数
                }
            }
        }
        return ans;

    }


    //测试
    public static  void main(String [] args){
        Eighttactics s = new Eighttactics();

        Scanner ss=new Scanner(System.in);
        System.out.println("请输入八卦阵的行数与列数");
        int x=ss.nextInt();
        int y=ss.nextInt();
        int [][]awarry=new int[x][y];//初始化数组
        System.out.println("请输入八卦阵元素");
        for(int i=0;i<x;i++)//循环输入
            for(int j=0;j<y;j++)
                awarry[i][j]=ss.nextInt();
        System.out.println("你输入的八卦阵为");
        for(int i=0;i<x;i++) {//循环输出
            for (int j = 0; j < y; j++)
                System.out.print(awarry[i][j] + "\t");
            System.out.println();
        }
        /*int max = 0;
        int min = 0x3f3f3f3f;*/
        //int [][] grid = {{1,1,0,0},{1,1,0,1},{1,0,0,1},{1,1,1,1}};
        //int [][] grid2 = {{1,0,3,3},{0,0,1,0},{1,1,0,1},{0,0,0,1}}; 测试用例
        //System.out.println(s.numIslands(grid));

       // System.out.println(s.numIslands(grid2));
        System.out.println(s.maxAndMin(awarry));  //ans为八卦阵的数量，比为8 否则不叫八卦阵

        System.out.println("最大兵力值："+ maxnum);
        System.out.println("最小兵力值："+ minNum);
    }
}

运行结果如下：

与题目测试范例结果一致：