アルゴリズム - あるサイズの対角線が行列内に同じ値であるかどうかを調べる

Question

私は以下の状況をどのように処理するのか分かりません：9*9行列と行列の要素があります。私は、要素が同じ値を持つ要素によって形成された（指定されたサイズの）対角の一部であるかどうかを調べる必要があります。例えば

：それは[7][5]がAの一部であることを意味するよりも私は[7][5]の要素、それに関連する値1、及び[8][4]に位置する要素の値、[6][6]、[5][7]、[4][8]は、また値1を持っている場合5要素を含む対角線

Javaでラインゲームを実装するには、このアルゴリズムが必要です。あなたはこの問題への正しいアプローチで私を助けてくれますか？ありがとう

Answer 1

まず、2つの対角線になることがあります。 最も簡単な解決策は、値 が異なるか、マトリックスの境界に当たるまで4つの可能な方向に拡大しています。両方のエンドポイントの境界である が終了した場合、それは対角線に属することを意味します。このため 擬似コードは、あなたの心のゲームの文脈では非常に 自然保管されている、すべてのこのような点を計算するために必要な場合には

boolean expands(x, y, dir_x, dir_y, matrix): 
    x1 = x 
    y1 = y 
    while positionInBorder(x1, y1): 
    if matrix[x][y] != matrix[x1][y1]: 
     return false 
    x1 += dir_x 
    y1 += dir_y  
    return true 

boolean inDiagonal(x, y, matrix): 
    return (expands(x, y, -1, -1, matrix) and expands(x, y, +1, +1, matrix)) or 
      (expands(x, y, +1, -1, matrix) and expands(x, y, -1, +1, matrix)) 

を次の可能性があるので、あなたは、より効率的なアルゴリズムを使用することができます。 あなたはすべての可能な対角線をチェックし、それらの値が同じであれば、その中のすべての要素の セットフラグ：

isInDiagonal[n][n] = False for all i, j. 
for start_position in top_row and left_column of matrix: 
    go down right while same value: 
     if reached bondary: 
     pass again and set isInDiagonal[x][y] for each item in diagonal 
for start_position in top_row and right_column of matrix: 
    go down left while same value: 
     if reached bondary: 
     pass again and set isInDiagonal[x][y] for each item in diagonal 

return isInDiagonal 

Answer 2

[x] [y]（あなたの例ではx = 7、y = 5）にいる場合、[x] [y]の値を持つまで4方向を検査したい]。その後、最大値を取る。

int t[][]; //that's the matrix 
int[] dx = new int[] { 1, -1, 1, -1 }; 
int[] dy = new int[] { -1, 1, 1, -1 }; 

static boolean checkBoundaries(int x, int y) { 
    return x >= 0 && x <= t.length && y >= 0 && y <= t[0].length 
} 

static int CountInDirection (int x, int y, int dir){ 
    int ret = 0; 
    int val = t[x][y]; 
    x+=dx[dir]; 
    y+=dy[dir]; 
    while(chechBoundaries(x,y) && t[x][y] == val) 
     ++ret; 

    return ret; 
} 

static void main(String[] args){ 
    int diag1 = CountInDirection (7,5,0) + CountInDirection (7,5,1); 
    int diag2 = CountInDirection (7,5,2) + CountInDirection (7,5,3); 
    System.out.println("Max diag is: " + Math.max(diag1, diag2)); 
}