首页 > 试题广场 >

数正方形

[问答题]

数正方形


【题目描述】

小B正在做一个关于图像理解方面的研究,她的目标是识别图像中的轮廓。当前阶段,她希望能够识别正方形。图像用一个矩阵表示,矩阵的每个元素对应于图像中的一个像素点,值为0或1,0表示背景,1表示前景。需要寻找的正方形必须满足线宽为单像素,且大小至少为2x2。她希望你能帮她找出图像中满足如下条件的两类正方形:

正方形的边与矩阵边缘平行;

正方形的边与矩阵对角线平行;

如以下矩阵中只有一个第一类正方形:

0000000

0111100

0100100

0100100

0111100

以下的矩阵中只有一个第二类正方形:

0000000

0010000

0101000

0010000

0000000

此外,不管何种类型的正方形,其每条边必须等长,且不能有任何边或顶点的像素与不属于该正方形的像素相连接。

输入

输入中有多组测试数据。第一行为一个整数t(1 =< t =< 10000),表示测试数据的组数,接下来是t组测试数据。每组测试数据的第一行为两个整数n和m(2<=n, m<=250),n和m分别为矩阵的行数和列数,接下来是n行数据,每行由m个0或1构成。

每个测试输入中的字符数不超过10^6个。

输出

对每组测试数据,在单独的行中输出矩阵中符合要求的正方形的数量。

样例输入

3

8 8

00010001

00101000

01000100

10000010

01000100

00101000

11010011

11000011

10 10

1111111000

1000001000

1011001000

1011001010

1000001101

1001001010

1010101000

1001001000

1000001000

1111111000

12 11

11111111111

10000000001

10111111101

10100000101

10101100101

10101100101

10100000101

10100000101

10111111101

10000000001

11111111111

00000000000

样例输出

1

2

3

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;     }
}

编辑于 2021-04-06 22:16:57 回复(1)
不会
发表于 2021-04-01 08:37:47 回复(0)