0

「チェッカーボード（2次元配列）の同じ行、列、または対角線に隣接するシンボルがk個ある場合にtrueを返すメソッドをJavaで記述します。ここで、kは必要なインラインシンボルの数です。」

これどうやってするの？行と列をチェックする方法については大まかな考えがありますが（非常に大まかな、コードはなく、考えだけです）、対角線をチェックするのは途方に暮れています。

編集：私が考えているもう1つの状況：任意の位置を確認するにはどうすればよいですか？現在、（0,0）から始まるオカレンスのみを検討していますが、たとえば（2,3）から（2,6）までの3の文字列がある場合はどうなりますか？複数の発生を追跡するにはどうすればよいですか？

編集：左対角線の検出（以下のコメントに投稿した質問の大まかなコード）：

LeftDiagonal(x, symbol) {
    noOfOccurence = 0;

    for (currentX = (size - 1); currentX >= x; currentX--) {
        if (board[currentX][currentX] == symbol) {
            noOfOccurence++;
        } else {
            break;
        }
    }

    return (noOfOccurence >= k);
}
4

4 に答える 4

2

頭に浮かぶ最も簡単な（バックトラックする可能性があるため、最も効率的ではありませんが）解決策は、次の擬似コードのような再帰関数を作成することです。

 FindAdjacent(x, y)
       if (matrix[x-1][y-1] == matrix[x][y])
            return 1 + FindAdjacent(x-1,y-1);
       .. Repeat for all 7 other adjacent locations (-1, +0) (+0, -1) (+1, -1) (-1, +1) (+1, +1) (+1, 0) (0, +1)
       else return 1;

このルーチンは、座標x、yが与えられると、その周りのシンボルを「ブロブ」で返します。
注：これは、3行などの記号をグループ化し、その横に1を下の列に配置することも意味します。

マトリックス内のすべての場所に対してこれを1回呼び出し、すべての再帰レベルが返された後の戻り値がであるかどうかを確認すると>= k、問題が解決する可能性があります。行列[-1][-1]などをチェックしないように、境界チェックを行うことを忘れないでください。

于 2012-10-15T01:18:29.410 に答える
0

あなたは私が想像する多くのネストされたループを実行することになります。すべての対角線を忘れないでください。

array[1][1] is just below array[0][1] above array[2][1] to the left of array[1][2] to the right of array[1][0] and diagonal to four different points:

diagonal up and to the left is array[0][0]
diagonal up and to the right is array[0][2]
down and to the left is array [2][0]
down and to the right is array[2][2]

[0][0] | [0][1] | [0][2]
[1][0] | [1][1] | [1][2]
[2][0] | [2][1] | [2][2]

たくさんグラフを作成すると、array[x][y]は誤解を招くと思います。array[row][column]の方が優れています。

于 2012-10-15T01:31:35.000 に答える
0

まず、あなたの「思考」を信用しないでください。実際のコードを書き出して、行と列のチェックが機能することを確認します。

アイデアは単純明快でなければなりません：

チェッカーボードをループします。左上が[0,0]であると仮定し、右の境界に達するまで右に進みます（[0,1]、[0,2] ...）。次に、次の行に進みます。右下のボックスに到達するまで終了します。

各ボックスについて、1。右、2。下、3。斜めから左下、4。斜めから右下のk個のオカレンスがあるかどうかを確認します。

4つのいずれかが発生した場合はtrueを返し、そうでない場合は次のセルに移動します。

例として、ここにいくつかのサンプル擬似コードがあります：

ボードを繰り返し処理します。

ROWS=8;
COLS=8;
char[ROWS][COLS] board;
k = 3; // occurrence

for (x = 0 to COLS-1) {
  for (y = 0 to ROWS-1) {
    checkRightward(x, y, k);
    // checkDownward(...)
  }
}

サンプルチェック右向き：

checkRightward(x,y,k) {
  char symbol = board[y][x];
  noOfOccurence = 0;
  for (currentX = x; currentX  < COLS ; ++currentX) {
    if (board[y][currentX] == symbol) {
      noOfOccurence++;
    } else {
      break; // jump out from the loop
    }
  }

  return (noOfOccurence >= k);
}

アイデアをJavaに変換し、他の不足しているチェックを追加するのは難しいことではありません。

編集：著者は私が話していることを本当に理解していないようです...それで私はアイデアについて少し視覚的なプレゼンテーションをします：

8 x 8のボードを想定すると、次のようになります。

           X
     0 1 2 3 4 5 6 7
  0
  1
  2
  3        * ---->
Y 4      / | \
  5   |/_  |  _\|
  6        V     
  7

上の図では、現在のセルの[x、y]座標（星印のある位置*）は[3,3]です。あなたがしなければならないことはチェックすることです

1）右向き：[3,3]、[4,3]、[5,3]....が同じ記号であるかどうかを確認することを意味します

2）下向き：[3,3]、[3,4]、[3,5]....が同じ記号であるかどうかを確認することを意味します

3）右対角：[3,3]、[4,4]、[5,5]....が同じ記号であるかどうかを確認することを意味します

4）左対角：[3,3]、[2,4]、[1,5]....が同じ記号であるかどうかを確認することを意味します

[0,0]セルからチェックを開始し、次に[1,0]、[2,0] ...、[0,1]、[1,1][2,1]...まで4つのチェックのいずれかが成功したセル、または最後のセル（[7,7]）にヒットしたセルが見つかりました。

于 2012-10-15T02:22:34.823 に答える
0 
for(i=0;i<row;i++)
For(j=0;j<column;j++){
current = Arr[row][col];
For(count=0;count<k;count++)
{
If(current==arr[row][col+count])
Flagcol=true
Else
Flagcol=false
}
For(count=0;count<k;count++)
{
If(current==arr[row+count][col])
Flagrow=true
else
Flagrow=false
}
For(count=0;count<k;count++)
{
If(current==arr[row+count][col+count])
Flagdiagnoltrue
Else 
Flagdiagnol=false
}
}
}

アイデアを与えるための非常に大まかなドラフト..そして、row + count / col+countがrow/count..else outofbondsexception..：-Dを超えてはならないかどうかを確認する必要があることを覚えておいてください。

于 2012-10-15T02:43:21.043 に答える