数正方形

package cn.ty.algo.algo.huawei;  import java.util.*;  /** * 数正方形 */ public class Test4 { static int[][] quard12X11 = new int[][]{
            {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},  {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},  {1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1},  {1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1},  {1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1},  {1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1},  {1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1},  {1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1},  {1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1},  {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},  {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    };    static int[][] quard10X10 = new int[][]{
            {1, 1, 1, 1, 1, 1, 1, 0, 0, 0},  {1, 0, 0, 0, 0, 0, 1, 0, 0, 0},  {1, 0, 1, 1, 0, 0, 1, 0, 0, 0},  {1, 0, 1, 1, 0, 0, 1, 0, 1, 0},  {1, 0, 0, 0, 0, 0, 1, 1, 0, 1},  {1, 0, 0, 1, 0, 0, 1, 0, 1, 0},  {1, 0, 1, 0, 1, 0, 1, 0, 0, 0},  {1, 0, 0, 1, 0, 0, 1, 0, 0, 0},  {1, 0, 0, 0, 0, 0, 1, 0, 0, 0},  {1, 1, 1, 1, 1, 1, 1, 0, 0, 0}
    };   static int[][] quard8X8 = new int[][]{
            {0,0,0,1,0,0,0,1},  {0,0,1,0,1,0,0,0},  {0,1,0,0,0,1,0,0},  {1,0,0,0,0,0,1,0},  {0,1,0,0,0,1,0,0},  {0,0,1,0,1,0,0,0},  {1,1,0,1,0,0,1,1},  {1,1,0,0,0,0,1,1}
    };   /**  * 矩阵对象  */  static class Martix {  int[][] martix;   int n;//行数     int m;//列数     List<Quard> quards = new ArrayList<>();   public Martix(int n, int m) {  this.m = m;  this.n = n;    martix = new int[n][m];    }  //往矩阵中添加一行数据    public void addLine(int lineNum, String line) {  char[] pixes = line.toCharArray();  for (int i = 0; i < pixes.length; i++) {  martix[lineNum][i] = Integer.parseInt(String.valueOf(pixes[i]));    }
    }  public int[][] getMartix() { return martix;  }  public void setArray(int[][] array){ this.martix = array;  }
} /** * 正方形对象  */  static class Quard {  /**
     *0表示非正方形  * 1表示1类正方形，即边与矩阵平行  * 2表示2类正方形，即边与矩阵对角线平行  */    int type = 0;   boolean hasBeenAdjoin = false;     Map<String, Point> points = new HashMap<>();     /**
      * 正方形四条边上的节点不能有不属于该正方形的相邻节点  */    boolean hasOtherPointAdjoin(int[][] matrix) {  int n= matrix.length;  int m = matrix[0].length;    Iterator<Map.Entry<String, Point>> it = points.entrySet().iterator();  while (it.hasNext()) {
                Point p = it.next().getValue();  int x = p.getX();  int y = p.getY();    //遍历周围八个节点    for (int i = -1; i < 2; i++) {  for (int k = -1; k < 2; k++) {  if(x+i<0||x+i>=n)continue;  if(y+k<0||y+k>=m)continue;  int px = matrix[x + i][y + k];    String key = (x + i) + "-" + (y + k);  if (px > 0 && !points.containsKey(key)) {  return true;   }
                    }
                }
        }  return false;    }  /**  * 正方形四条边总像素符合4n-4规律  * @param n 矩阵较短的一条边  **/    boolean pointSumInRegular(int n){  for(int i=2;i<=n;i++){  int sum = 4*i-4;  if(points.size()==sum) return true;  }  return false;  } public int getType(){ return type;  } public void setPoint(int x, int y) {
         String key = x + "-" + y;    points.put(key, new Point(x, y));  }  public void setType(int t) { this.type = t;  }  /**  * 判断给定的节点是否与points容器中的节点相邻  */    public boolean adjoiningPoints(int x, int y) {  int type = 0;    //正方位关系    if (points.containsKey((x - 1) + "-" + y)) type++;  if (points.containsKey((x + 1) + "-" + y)) type++;  if (points.containsKey(x + "-" + (y - 1))) type++;  if (points.containsKey(x + "-" + (y + 1))) type++;    //斜方位关系    if (points.containsKey((x - 1) + "-" + (y + 1))) type++;  if (points.containsKey((x - 1) + "-" + (y - 1))) type++;  if (points.containsKey((x + 1) + "-" + (y - 1))) type++;  if (points.containsKey((x + 1) + "-" + (y + 1))) type++;   return type>0?true:false;    }  public void setHasBeenAdjoin(boolean b){ this.hasBeenAdjoin = b;  }  public boolean getHasBeenAdjoin(){ return this.hasBeenAdjoin;  }

    }  /**  * 组成正方形的点对象  */    static class Point {  int x;  int y;   public boolean equals(Object o) {  if (o instanceof Point) {
                Point p = (Point) o;  if (p.getX() == x && p.getY() == y) {  return true;   }
            }  return false;    }  public int hashCode() {  return (x + "-" + y).hashCode();    }  public Point(int x, int y) {  this.x = x;  this.y = y;    }  public int getX() { return x;  }  public int getY() { return y;  }
    }  public static void main(String[] args) {
        List<Martix> martixes = new ArrayList<>();     //接收数据---start    if(false){
            Scanner sc = new Scanner(System.in);  if (sc.hasNext()) {  int groupNum = sc.nextInt();  for (int i = 0; i < groupNum; i++) {  if (sc.hasNext()) {
                        String n_m = sc.nextLine();    String[] nmStr = n_m.split(" ");  int n = Integer.parseInt(nmStr[0]);//行数    int m = Integer.parseInt(nmStr[1]);    Martix martix = new Martix(n, m);    martixes.add(martix);  for (int k = 0; k < n; k++) {  if (sc.hasNext()) {
                                String line = sc.nextLine();    martix.addLine(k, line);    }
                        }
                    }
                }
            }  //接收数据---end    for (int i = 0; i < martixes.size(); i++) {  countQuard(martixes.get(i));  }
        } else {  //本地测试     Martix martix = new Martix(quard12X11.length,quard12X11[1].length);    martix.setArray(quard12X11);  countQuard(martix);  }

    }  /**  * 统计正方形  */    public static void countQuard(Martix martix) {
        List<Quard> unconfirmedQuard = new ArrayList<>();//用于存储可能是正方形的容器    List<Quard> confirmedQuard = new ArrayList<>();//用于存储最后符合条件的正方形容器  //按行遍历矩阵    int[][] martixArray = martix.getMartix();  for (int i = 0; i < martix.n; i++) {  int[] line = martixArray[i];  for (int j = 0; j < line.length; j++) {  int p = line[j];  if (p == 0) continue;  if(!pointInQuard(i,j,unconfirmedQuard)){  //像素不属于已探测到的正方形    Quard quard = new Quard();    unconfirmedQuard.add(quard);  int type = 0;  if(j==0) type=1;//第一列的像素探测到的要么是一类正方形，要么是非正方形    if(j==line.length-1) continue;//最后一列跳过，要么是孤点，要么是归属已检测到正方形    if(i==martixArray.length-1)continue;//最后一行跳过，要么是孤点，要么是归属已检测到正方形    if(i==0&&j>0&&line[j+1]==0) type=2;//第一行位置大于0的像素，右边是背景的话一定是二类正方形    if(i>0&&j>0&&martixArray[i][j+1]==1&&martixArray[i+1][j]==1) type=1;  if(i>0&&j>0&&martixArray[i+1][j-1]==1&&martixArray[i+1][j+1]==1) type=2;    quard.setType(type);    quard.setPoint(i,j);  }
            }
        }  //过滤，正方形不能相邻,正方形节点数符合条件4n-4(n>2)    for(int i=0;i<unconfirmedQuard.size();i++){
            Quard quard = unconfirmedQuard.get(i);  if((quard.getType()==1||quard.getType()==2)
                    &&!quard.hasOtherPointAdjoin(martixArray)
                    &&quard.pointSumInRegular(Math.min(martix.m, martix.n))
                    &&!quard.getHasBeenAdjoin()
            ){
                confirmedQuard.add(quard);  }
        }
        System.out.println(confirmedQuard.size());    }  /**  * 判断当前像素是否属与某个Quard对象存在相邻关系  */    public static boolean pointInQuard(int x, int y, List<Quard> quards) {
        List<Quard> adjoinQuards = new ArrayList<>();  for (int i = 0; i < quards.size(); i++) {
            Quard quard = quards.get(i);  if (quard.adjoiningPoints(x, y)) {  //只要存在相邻关系，就认为这个像素属于这个Quard对象    quard.setPoint(x, y);    adjoinQuards.add(quard); 
      }
        }  if(adjoinQuards.size()>1){  for(int i=0;i<adjoinQuards.size();i++){
                adjoinQuards.get(i).setHasBeenAdjoin(true);    }
        }  return adjoinQuards.size()>0?true:false;     }
}