在二维数组中查找相邻的数字，可以是对角线、水平或垂直的。

Question

我正在制作一个19x19的棋盘游戏，它基本上是五子棋，叫做Gomoku。

我想设计一个高效的算法来查找是否有'n'个棋子在一行。数据存储为19x19的二维数组。但出于问题的考虑，让我们假设它是6x6。

0 0 0 1 0 0      0 0 0 0 0 0
0 0 0 1 0 0      0 1 0 0 0 0
0 0 0 1 0 0      0 0 1 0 0 0
0 0 0 1 0 0      0 0 0 1 0 0 
0 0 0 1 0 0      0 0 0 0 1 0
0 0 0 0 0 0      0 0 0 0 0 1

这是两个连续的1的“5”的例子。如何测试水平、垂直和两个对角线？

以下是我低效的代码：

 private boolean firstDiagonalCheck(int x, int y, int num) {
    int count = 1;
    int check = 0;
    boolean rflag = true;
    boolean lflag = true;
    int pos = 1;

    check = turnHuman + 1;

    while (rflag) {
        if (x + pos >= 19 || y + pos >= 19) {
            rflag = false;
            break;
        }
        if (gb.getBoard()[x + pos][y + pos] == check) {
            count++;
            pos++;
        } else {
            rflag = false;
        }
    }

    pos = 1;

    while (lflag) {
        if (x - pos < 0 || y - pos < 0) {
            lflag = false;
            break;
        }
        if (gb.getBoard()[x - pos][y - pos] == check) {
            count++;
            pos++;
        } else {
            lflag = false;
        }
    }

    if (count == num) {
        return true;
    }
    return false;
}

这只是第一种对角线的方法，还有另外三种方法。

如何使其更有效率并检查所有4个方向？

编辑##################

我的代码实现了以下功能： - 获取棋子的位置(x,y) - 检查两侧(如果是垂直方向则为上下)，并计算出连续相同棋子的数量 - 如果计数匹配所需的数字("num")，则返回true，否则返回false。

如果每次都检查整个棋盘以查看是否有连续的棋子，是否会更有效率？

- Michael Halper

---

你想同时检查4个条件吗？ - Kick Buttowski

好的，它应该检查所有4个条件。无论它是一个一个地检查还是同时检查，但一定有更好的方法！ - Michael Halper

如果你最终要检查整个棋盘，那么只需扫描每一行、每一列和对角线会更有效率。但是，如果你只想查看最近的棋子是否创建了5个连续的棋子（并且可以假设如果在棋盘上其他地方已经有5个连续的棋子，则已经被识别），那么只需检查该点周围的情况将更有效率，因为你可以消除大部分搜索空间。 - Tim

如果您愿意更改棋盘的表示方式，可以考虑使用位棋盘以获得更快的性能：https://dev59.com/BVrUa4cB1Zd3GeqPhjes#7046415。 - emsworth

@emsworth 好的！在我开始其他工作之前，我一定会先研究一下位棋盘。我想使用二维数组是为了简单起见。还有其他数据结构可能更有效吗？ - Michael Halper

如果你指的是时间效率，我不确定（我不这么认为）；许多国际象棋引擎使用位板表示法。你可以预缓存许多位板以进行各种查找，但它的空间效率较低。但你是对的，它不像二维数组那样直观易懂。 - emsworth

Answer 1

int count=0;
boolean Check(int x,int y)
{  
  int p1;
  int p2;
 if(elementat[x+1][y+1]==1)
  {p1=1; p2=1;}
else   if(elementat[x+1][y]==1)
  {p1=1; p2=0;}
else.  if(elementat[x+1][y-1]==1)
   {p1=1; p2=-1;}
else.  if(elementat[x][y-1]==1)
   {p1=0;p2=-1;}
else.  if(elementat[x-1][y-1]==1)
   {p1=-1; p2=-1;}
else.  if(elementat[x-1][y]==1)
   {p1=-1; p2=0;}
else.  if(elementat[x-1][y+1]==1)
   {p1=-1; p2=1;}
else.  if(elementat[x][y+1]==1)
  {p1=0; p2=1;}

Checknext(x,y);
Checknextinv(x,y);
If(count==5) // 5 means no. of elements to form line
{return true}
else 
   {return false;}
}


Checknext(x,y)  //19 represents the 19x19 matrix
{ if((x+p1)<=19 && (x+p1)>=0 && (y+p2)<=19 && (y+p2)>=0)
      {     if(element[x+p1][y+p2]==1)
             {  count++;
               checknext[x+p1][y+p2];
      }
}
Checknextinv(x,y)
{ if( (x+(-1*p1))<=19 && (x+(-1*p1))>=0 && (y+(-1*p2))<=19 && (y+(-1*p2))>=0))
    {
      if(element[x+(-1*p1)][y+(-1*p2)]==1 )
         {
               count++;
                checknextinv[x+(-1*p1)][y+(-1*p2)];
        }
 }

- Ankit