所以我有一个 N×M 的矩阵。在给定位置,我有一个代表颜色的值。如果此时没有任何内容,则值为 -1
。我需要做的是在我添加一个新点之后,检查他所有具有相同颜色值的邻居,如果超过 2 个,则将它们都设置为 -1
。
如果我所说的没有意义,我正在尝试做的是一种算法,我用它来消除屏幕上所有相同颜色的气泡,其中气泡存储在一个矩阵中,其中 -1
表示没有气泡,{0,1,2,...}
表示有一个特定颜色的气泡。
此外,如果您有任何建议,我将不胜感激。谢谢。 这是我尝试过但失败了的:
public class Testing {
static private int[][] gameMatrix=
{{3, 3, 4, 1, 1, 2, 2, 2, 0, 0},
{1, 4, 1, 4, 2, 2, 1, 3, 0, 0},
{2, 2, 4, 4, 3, 1, 2, 4, 0, 0},
{0, 4, 2, 3, 4, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
};
static int Rows=6;
static int Cols=10;
static int count;
static boolean[][] visited=new boolean[15][15];
static int NOCOLOR = -1;
static int color = 1;
public static void dfs(int r, int c, int color, boolean set)
{
for(int dr = -1; dr <= 1; dr++)
for(int dc = -1; dc <= 1; dc++)
if(!(dr == 0 && dc == 0) && ok(r+dr, c+dc))
{
int nr = r+dr;
int nc = c+dc;
// if it is the same color and we haven't visited this location before
if(gameMatrix[nr][nc] == color && !visited[nr][nc])
{
visited[nr][nc] = true;
count++;
dfs(nr, nc, color, set);
if(set)
{
gameMatrix[nr][nc] = NOCOLOR;
}
}
}
}
static boolean ok(int r, int c)
{
return r >= 0 && r < Rows && c >= 0 && c < Cols;
}
static void showMatrix(){
for(int i = 0; i < gameMatrix.length; i++) {
System.out.print("[");
for(int j = 0; j < gameMatrix[0].length; j++) {
System.out.print(" " + gameMatrix[i][j]);
}
System.out.println(" ]");
}
System.out.println();
}
static void putValue(int value,int row,int col){
gameMatrix[row][col]=value;
}
public static void main(String[] args){
System.out.println("Initial Matrix:");
putValue(1, 4, 1);
putValue(1, 5, 1);
putValue(1, 4, 2);
showMatrix();
for(int n = 0; n < Rows; n++)
for(int m = 0; m < Cols; m++)
visited[n][m] = false;
//reset count
count = 0;
dfs(5,1,color,false);
//if there are more than 2 set the color to NOCOLOR
for(int n = 0; n < Rows; n++)
for(int m = 0; m < Cols; m++)
visited[n][m] = false;
if(count > 2)
{
dfs(5,1,color,true);
}
System.out.println("Matrix after dfs:");
showMatrix();
}
}
最佳答案
您遇到的一个问题是您没有检查上一行和最左边的列:
static boolean ok(int r, int c)
{
return r > 0 && r < Rows && c > 0 && c < Cols;
}
你应该检查 r >= 0
, c>= 0
第二个问题是您使用了两次 dfs()
,但是 visited
字段是静态的 - 它全部设置为 true
在第二次运行 dfs()
之前,您需要在第二次运行之前将所有字段中的它初始化回 false
,否则算法将立即终止而不会做任何事 [因为所有节点都已在 visited
中 - 并且算法将决定不重新探索这些节点。]。
关于java - 深度优先搜索错误?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9428068/