给定一个矩阵，查找所有相邻的相同元素

bejyjqdl 于 2021-09-13 发布在 Java

关注(0)|答案(2)|浏览(305)

我有一个2d矩阵，现在我想选择一个元素 e 查看所有相邻元素（i+1，j），（i-1，j），（i，j+1），（i，j-1），如果它们与 e 数一数有多少是这样匹配的。现在找到可能的最大计数。
例子：

产出：5。
因为4是重复5次的元素，所有元素都是邻接的，而1只出现2次，2只出现3次。
如何解决这个问题？我尝试过bfs，但在如何保持计数方面遇到了问题？

static class pair {
    int first, second;

    public pair(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

static int ROW = 4;
static int COL = 4;

// Direction vectors
static int dRow[] = { -1, 0, 1, 0 };
static int dCol[] = { 0, 1, 0, -1 };

// Function to check if a cell
// is be visited or not
static boolean isValid(boolean vis[][], int row, int col) {

    // If cell lies out of bounds
    if (row < 0 || col < 0 || row >= ROW || col >= COL)
        return false;

    // If cell is already visited
    if (vis[row][col])
        return false;

    // Otherwise
    return true;
}

 static void BFS(int grid[][], boolean vis[][], int row, int col) {
    // Stores indices of the matrix cells
    Queue<pair> q = new LinkedList<>();

    // Mark the starting cell as visited
    // and push it into the queue
    q.add(new pair(row, col));
    vis[row][col] = true;

    // Iterate while the queue
    // is not empty
    int max = 0;
    while (!q.isEmpty()) {
        pair cell = q.peek();
        int x = cell.first;
        int y = cell.second;

        int v = grid[x][y];
        System.out.print(grid[x][y] + " ");

        // Go to the adjacent cells
        for (int i = 0; i < 4; i++) {
            int adjx = x + dRow[i];
            int adjy = y + dCol[i];

            if (isValid(vis, adjx, adjy)) {
                if (grid[adjx][adjx] == v) {
                    q.add(new pair(adjx, adjy));
                    vis[adjx][adjy] = true;
                }

            }
        }
    }

public static void main(String[] args) {

    // Given input matrix
    int grid[][] = { .... };
    ROW = grid.length;
    COL = grid[0].length;
    // Declare the visited array
    boolean[][] vis = new boolean[ROW][COL];

    BFS(grid, vis, 0, 0);
}

Java Algorithm

来源：https://stackoverflow.com/questions/68535976/given-a-matrix-find-all-adjacent-same-elements

2条答案

按热度按时间

eivgtgni1#

您需要在网格上迭代以确定每个bfs的起点。此外，您还需要在每个bfs的开始处初始化一个新计数，并在每次访问相邻单元时递增该计数。然后取每个此类计数的最大值。

static int max(int[][] grid)
{
    int rows = grid.length;
    int cols = grid[0].length;

    Queue<Pos> q = new LinkedList<>();
    boolean[][] visited = new boolean[rows][cols];

    int max = 0;
    for(int r=0; r<rows; r++)
    {
        for(int c=0; c<cols; c++)
        {
            if(!visited[r][c])
            {
                q.add(new Pos(r, c));
                visited[r][c] = true;

                int count = 0;
                while(!q.isEmpty())
                {
                    Pos p = q.poll();
                    count += 1;

                    for(int d=0; d<4; d++)
                    {
                        int i = p.r + dRow[d];
                        int j = p.c + dCol[d];

                        if(i >= 0 && i < rows && j >= 0 && j < cols && !visited[i][j] && grid[i][j] == grid[r][c]) 
                        {
                            q.add(new Pos(i, j));
                            visited[i][j] = true;
                        }
                    }
                }
                max = Math.max(max, count);
            }
        }
    }
    return max;
}

测试：

int[][] grid = {{1,2,3,4},
                {1,2,4,4},
                {4,2,4,5},
                {6,9,4,7}};

System.out.printf("Max = %d%n", max(grid));

输出：

Max = 5

赞(0）回复(0）举报 2021-09-13

y1aodyip2#

简单！

public static int findMaxAdjacentCount(int[][] grid) {
    boolean[][] visited = createVisitGrid(grid);
    int res = 0;

    for (int row = 0; row < grid.length; row++)
        for (int col = 0; col < grid[row].length; col++)
            if (!visited[row][col])
                res = Math.max(res, dfs(grid, visited, grid[row][col], row, col));

    return res;
}

private static int dfs(int[][] grid, boolean[][] visited, int expected, int row, int col) {
    if (row < 0 || row >= grid.length)
        return 0;
    if (col < 0 || col >= grid[row].length)
        return 0;
    if (visited[row][col] || grid[row][col] != expected)
        return 0;

    visited[row][col] = true;

    int depth = 1;
    depth += dfs(grid, visited, expected, row, col - 1);
    depth += dfs(grid, visited, expected, row, col + 1);
    depth += dfs(grid, visited, expected, row - 1, col);
    depth += dfs(grid, visited, expected, row + 1, col);
    return depth;
}

private static boolean[][] createVisitGrid(int[][] grid) {
    boolean[][] visit = new boolean[grid.length][];

    for (int row = 0; row < grid.length; row++)
        visit[row] = new boolean[grid[row].length];

    return visit;
}

赞(0）回复(0）举报 2021-09-13

我来回答

给定一个矩阵，查找所有相邻的相同元素

2条答案

相关问题

热门标签

最新问答