2 차원 배열의 모든 "1"이 직사각형을 구성하는지 확인하는 알고리즘

Question

2 차원 정수 배열이 주어진 경우 모든 요소가 1과 동일하다는 것을 확인하는 방법을 정의하여 직사각형을 만듭니다.

이

내가 지금까지 해낸 것입니다 :

public static boolean oneRectangle(int [][] a) { 
    boolean rectangle=true; 
    int[][] res; 
    int OneinRow=0; //keeps track of how many ones there are in the row 
    int OneinColoumn=0; //keeps track of how many ones there are in a coloumn 

    for(int i=0; i<a.length; i++) { 
     for (int j = 0; j < a[0].length; j++) { 
      while (a[i][j] == 1) { 
       i++; 
       OneinRow++; 
      } 
      while (a[i][j] == 1) { 
       j++; 
       OneinColoumn++; 
      } 
     } 
    } 
    res = new int[OneinRow][OneinColoumn]; 

    for(int k=0; k<res.length; k++) 
     for(int l=0; l<res[0].length; l++) 
      if(res[k][l] != 1) 
       rectangle = false; 

    return rectangle; 
} 

가 예상대로 작동하지 않기 때문에

f = new int[][] { 
      {1,2,3,4}, //1 in position 0 
      {2,1,4,5}, //1 in position 1 
      {3,4,5,6}}; 

반품 true 대신 false .

어떻게 수정하고 알고리즘을 개선 할 수 있습니까?

Answer 1

행 및 열당 1을 계산하는 것만으로는 충분하지 않습니다.

나는 이런 식 수행 전체 배열을 통해

루프와 1가 발생한 각 차원의 최고와 최저 지수를 추적. 또한 1을 모두 셉니다.

끝에는 1의 수가 각 차원에 대한 가장 높은 색인과 가장 낮은 색인의 차이와 같아야합니다.

int minx=Integer.MAX_VALUE; 
int maxx=-1; 
int miny=Integer.MAX_VALUE; 
int maxy=-1; 
int count=0; 
for x=0... 
    for y=0... 
    if(1==a[x][y]{ 
     minx=Math.min(minx,x); 
     maxx=Math.max(maxx,x); 
     miny=Math.min(miny,y); 
     maxy=Math.max(maxy,y); 
     count ++; 
    } 

return count==(maxx-minx+1)*(maxy-miny+1); 

추신 : 2 차원 어레이

적어도 하나가있는 경우 수표를 추가 할 수 있습니다.