电网上最大的连接部件
给定不同单元格中不同颜色的网格，每种颜色由不同的数字表示。任务是找出网格上最大的连接组件。最大组件网格指的是一个最大的单元格集，这样，您只需在该集中相邻的单元格之间移动，就可以从任何单元格移动到该集中的任何其他单元格。 例:
输入:
不同颜色的网格
输出:9
网格的最大连通分量
方法: 该方法是将给定的网格可视化为一个图，其中每个单元代表该图的一个单独节点，每个节点连接到该网格紧接的上、下、左、右四个其他节点。现在进行 BFS 搜索图的每个节点，找到所有连接到当前节点的节点，其颜色值与当前节点相同。 以上示例的图表如下:
网格的图形表示
。 在每个细胞(I，j)，一个 BFS 可以完成。从一个单元格可能移动到右侧、左侧、顶部或底部。仅移动到范围内颜色相同的单元格。如果先前访问过相同的节点，则网格的最大分量值存储在结果[][] 数组中。使用记忆，减少任何细胞上的 BFS 数。visited【】【】数组用于标记该单元之前是否被访问过，并在对每个单元进行 BFS 时计数存储连接组件的计数。存储最大计数，并使用 result[][]数组打印结果网格。 以下是上述方法的说明:
C++
// CPP program to print the largest
// connected component in a grid
#include <bits/stdc++.h>
using namespace std;
const int n = 6;
const int m = 8;
// stores information about which cell
// are already visited in a particular BFS
int visited[n][m];
// result stores the final result grid
int result[n][m];
// stores the count of cells in the largest
// connected component
int COUNT;
// Function checks if a cell is valid i.e it
// is inside the grid and equal to the key
bool is_valid(int x, int y, int key, int input[n][m])
{
if (x < n && y < m && x >= 0 && y >= 0) {
if (visited[x][y] == false && input[x][y] == key)
return true;
else
return false;
}
else
return false;
}
// BFS to find all cells in
// connection with key = input[i][j]
void BFS(int x, int y, int i, int j, int input[n][m])
{
// terminating case for BFS
if (x != y)
return;
visited[i][j] = 1;
COUNT++;
// x_move and y_move arrays
// are the possible movements
// in x or y direction
int x_move[] = { 0, 0, 1, -1 };
int y_move[] = { 1, -1, 0, 0 };
// checks all four points connected with input[i][j]
for (int u = 0; u < 4; u++)
if (is_valid(i + y_move[u], j + x_move[u], x, input))
BFS(x, y, i + y_move[u], j + x_move[u], input);
}
// called every time before a BFS
// so that visited array is reset to zero
void reset_visited()
{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
visited[i][j] = 0;
}
// If a larger connected component
// is found this function is called
// to store information about that component.
void reset_result(int key, int input[n][m])
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] && input[i][j] == key)
result[i][j] = visited[i][j];
else
result[i][j] = 0;
}
}
}
// function to print the result
void print_result(int res)
{
cout << "The largest connected "
<< "component of the grid is :" << res << "\n";
// prints the largest component
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (result[i][j])
cout << result[i][j] << " ";
else
cout << ". ";
}
cout << "\n";
}
}
// function to calculate the largest connected
// component
void computeLargestConnectedGrid(int input[n][m])
{
int current_max = INT_MIN;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
reset_visited();
COUNT = 0;
// checking cell to the right
if (j + 1 < m)
BFS(input[i][j], input[i][j + 1], i, j, input);
// updating result
if (COUNT >= current_max) {
current_max = COUNT;
reset_result(input[i][j], input);
}
reset_visited();
COUNT = 0;
// checking cell downwards
if (i + 1 < n)
BFS(input[i][j], input[i + 1][j], i, j, input);
// updating result
if (COUNT >= current_max) {
current_max = COUNT;
reset_result(input[i][j], input);
}
}
}
print_result(current_max);
}
// Drivers Code
int main()
{
int input[n][m] = { { 1, 4, 4, 4, 4, 3, 3, 1 },
{ 2, 1, 1, 4, 3, 3, 1, 1 },
{ 3, 2, 1, 1, 2, 3, 2, 1 },
{ 3, 3, 2, 1, 2, 2, 2, 2 },
{ 3, 1, 3, 1, 1, 4, 4, 4 },
{ 1, 1, 3, 1, 1, 4, 4, 4 } };
// function to compute the largest
// connected component in the grid
computeLargestConnectedGrid(input);
return 0;
}
Java 语言(一种计算机语言，尤用于创建网站)
// Java program to print the largest
// connected component in a grid
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
static final int n = 6;
static final int m = 8;
// stores information about which cell
// are already visited in a particular BFS
static final int visited[][] = new int [n][m];
// result stores the final result grid
static final int result[][] = new int [n][m];
// stores the count of
// cells in the largest
// connected component
static int COUNT;
// Function checks if a cell
// is valid i.e it is inside
// the grid and equal to the key
static boolean is_valid(int x, int y,
int key,
int input[][])
{
if (x < n && y < m &&
x >= 0 && y >= 0)
{
if (visited[x][y] == 0 &&
input[x][y] == key)
return true;
else
return false;
}
else
return false;
}
// BFS to find all cells in
// connection with key = input[i][j]
static void BFS(int x, int y, int i,
int j, int input[][])
{
// terminating case for BFS
if (x != y)
return;
visited[i][j] = 1;
COUNT++;
// x_move and y_move arrays
// are the possible movements
// in x or y direction
int x_move[] = { 0, 0, 1, -1 };
int y_move[] = { 1, -1, 0, 0 };
// checks all four points
// connected with input[i][j]
for (int u = 0; u < 4; u++)
if ((is_valid(i + y_move[u],
j + x_move[u], x, input)) == true)
BFS(x, y, i + y_move[u],
j + x_move[u], input);
}
// called every time before
// a BFS so that visited
// array is reset to zero
static void reset_visited()
{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
visited[i][j] = 0;
}
// If a larger connected component
// is found this function is
// called to store information
// about that component.
static void reset_result(int key,
int input[][])
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visited[i][j] ==1 &&
input[i][j] == key)
result[i][j] = visited[i][j];
else
result[i][j] = 0;
}
}
}
// function to print the result
static void print_result(int res)
{
System.out.println ("The largest connected " +
"component of the grid is :" +
res );
// prints the largest component
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (result[i][j] != 0)
System.out.print(result[i][j] + " ");
else
System.out.print(". ");
}
System.out.println();
}
}
// function to calculate the
// largest connected component
static void computeLargestConnectedGrid(int input[][])
{
int current_max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
reset_visited();
COUNT = 0;
// checking cell to the right
if (j + 1 < m)
BFS(input[i][j], input[i][j + 1],
i, j, input);
// updating result
if (COUNT >= current_max)
{
current_max = COUNT;
reset_result(input[i][j], input);
}
reset_visited();
COUNT = 0;
// checking cell downwards
if (i + 1 < n)
BFS(input[i][j],
input[i + 1][j], i, j, input);
// updating result
if (COUNT >= current_max)
{
current_max = COUNT;
reset_result(input[i][j], input);
}
}
}
print_result(current_max);
}
// Driver Code
public static void main(String args[])
{
int input[][] = {{1, 4, 4, 4, 4, 3, 3, 1},
{2, 1, 1, 4, 3, 3, 1, 1},
{3, 2, 1, 1, 2, 3, 2, 1},
{3, 3, 2, 1, 2, 2, 2, 2},
{3, 1, 3, 1, 1, 4, 4, 4},
{1, 1, 3, 1, 1, 4, 4, 4}};
// function to compute the largest
// connected component in the grid
computeLargestConnectedGrid(input);
}
}
// This code is contributed by Subhadeep
Python 3
# Python3 program to print the largest
# connected component in a grid
n = 6;
m = 8;
# stores information about which cell
# are already visited in a particular BFS
visited = [[0 for j in range(m)]for i in range(n)]
# result stores the final result grid
result = [[0 for j in range(m)]for i in range(n)]
# stores the count of cells in the largest
# connected component
COUNT = 0
# Function checks if a cell is valid i.e it
# is inside the grid and equal to the key
def is_valid(x, y, key, input):
if (x < n and y < m and x >= 0 and y >= 0):
if (visited[x][y] == 0 and input[x][y] == key):
return True;
else:
return False;
else:
return False;
# BFS to find all cells in
# connection with key = input[i][j]
def BFS(x, y, i, j, input):
global COUNT
# terminating case for BFS
if (x != y):
return;
visited[i][j] = 1;
COUNT += 1
# x_move and y_move arrays
# are the possible movements
# in x or y direction
x_move = [ 0, 0, 1, -1 ]
y_move = [ 1, -1, 0, 0 ]
# checks all four points connected with input[i][j]
for u in range(4):
if (is_valid(i + y_move[u], j + x_move[u], x, input)):
BFS(x, y, i + y_move[u], j + x_move[u], input);
# called every time before a BFS
# so that visited array is reset to zero
def reset_visited():
for i in range(n):
for j in range(m):
visited[i][j] = 0
# If a larger connected component
# is found this function is called
# to store information about that component.
def reset_result(key, input):
for i in range(n):
for j in range(m):
if (visited[i][j] != 0 and input[i][j] == key):
result[i][j] = visited[i][j];
else:
result[i][j] = 0;
# function to print the result
def print_result(res):
print("The largest connected "+
"component of the grid is :" + str(res));
# prints the largest component
for i in range(n):
for j in range(m):
if (result[i][j] != 0):
print(result[i][j], end = ' ')
else:
print('. ',end = '')
print()
# function to calculate the largest connected
# component
def computeLargestConnectedGrid(input):
global COUNT
current_max = -10000000000
for i in range(n):
for j in range(m):
reset_visited();
COUNT = 0;
# checking cell to the right
if (j + 1 < m):
BFS(input[i][j], input[i][j + 1], i, j, input);
# updating result
if (COUNT >= current_max):
current_max = COUNT;
reset_result(input[i][j], input);
reset_visited();
COUNT = 0;
# checking cell downwards
if (i + 1 < n):
BFS(input[i][j], input[i + 1][j], i, j, input);
# updating result
if (COUNT >= current_max):
current_max = COUNT;
reset_result(input[i][j], input);
print_result(current_max);
# Drivers Code
if __name__=='__main__':
input = [ [ 1, 4, 4, 4, 4, 3, 3, 1 ],
[ 2, 1, 1, 4, 3, 3, 1, 1 ],
[ 3, 2, 1, 1, 2, 3, 2, 1 ],
[ 3, 3, 2, 1, 2, 2, 2, 2 ],
[ 3, 1, 3, 1, 1, 4, 4, 4 ],
[ 1, 1, 3, 1, 1, 4, 4, 4 ] ];
# function to compute the largest
# connected component in the grid
computeLargestConnectedGrid(input);
# This code is contributed by pratham76
C
// C# program to print the largest
// connected component in a grid
using System;
class GFG
{
public const int n = 6;
public const int m = 8;
// stores information about which cell
// are already visited in a particular BFS
public static readonly int[][] visited =
RectangularArrays.ReturnRectangularIntArray(n, m);
// result stores the final result grid
public static readonly int[][] result =
RectangularArrays.ReturnRectangularIntArray(n, m);
// stores the count of cells in the
// largest connected component
public static int COUNT;
// Function checks if a cell is valid i.e
// it is inside the grid and equal to the key
internal static bool is_valid(int x, int y,
int key, int[][] input)
{
if (x < n && y < m &&
x >= 0 && y >= 0)
{
if (visited[x][y] == 0 &&
input[x][y] == key)
{
return true;
}
else
{
return false;
}
}
else
{
return false;
}
}
// BFS to find all cells in
// connection with key = input[i][j]
public static void BFS(int x, int y, int i,
int j, int[][] input)
{
// terminating case for BFS
if (x != y)
{
return;
}
visited[i][j] = 1;
COUNT++;
// x_move and y_move arrays
// are the possible movements
// in x or y direction
int[] x_move = new int[] {0, 0, 1, -1};
int[] y_move = new int[] {1, -1, 0, 0};
// checks all four points
// connected with input[i][j]
for (int u = 0; u < 4; u++)
{
if ((is_valid(i + y_move[u],
j + x_move[u], x, input)) == true)
{
BFS(x, y, i + y_move[u],
j + x_move[u], input);
}
}
}
// called every time before
// a BFS so that visited
// array is reset to zero
internal static void reset_visited()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
visited[i][j] = 0;
}
}
}
// If a larger connected component is
// found this function is called to
// store information about that component.
internal static void reset_result(int key,
int[][] input)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visited[i][j] == 1 &&
input[i][j] == key)
{
result[i][j] = visited[i][j];
}
else
{
result[i][j] = 0;
}
}
}
}
// function to print the result
internal static void print_result(int res)
{
Console.WriteLine("The largest connected " +
"component of the grid is :" + res);
// prints the largest component
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (result[i][j] != 0)
{
Console.Write(result[i][j] + " ");
}
else
{
Console.Write(". ");
}
}
Console.WriteLine();
}
}
// function to calculate the
// largest connected component
public static void computeLargestConnectedGrid(int[][] input)
{
int current_max = int.MinValue;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
reset_visited();
COUNT = 0;
// checking cell to the right
if (j + 1 < m)
{
BFS(input[i][j], input[i][j + 1],
i, j, input);
}
// updating result
if (COUNT >= current_max)
{
current_max = COUNT;
reset_result(input[i][j], input);
}
reset_visited();
COUNT = 0;
// checking cell downwards
if (i + 1 < n)
{
BFS(input[i][j], input[i + 1][j],
i, j, input);
}
// updating result
if (COUNT >= current_max)
{
current_max = COUNT;
reset_result(input[i][j], input);
}
}
}
print_result(current_max);
}
public static class RectangularArrays
{
public static int[][] ReturnRectangularIntArray(int size1,
int size2)
{
int[][] newArray = new int[size1][];
for (int array1 = 0; array1 < size1; array1++)
{
newArray[array1] = new int[size2];
}
return newArray;
}
}
// Driver Code
public static void Main(string[] args)
{
int[][] input = new int[][]
{
new int[] {1, 4, 4, 4, 4, 3, 3, 1},
new int[] {2, 1, 1, 4, 3, 3, 1, 1},
new int[] {3, 2, 1, 1, 2, 3, 2, 1},
new int[] {3, 3, 2, 1, 2, 2, 2, 2},
new int[] {3, 1, 3, 1, 1, 4, 4, 4},
new int[] {1, 1, 3, 1, 1, 4, 4, 4}
};
// function to compute the largest
// connected component in the grid
computeLargestConnectedGrid(input);
}
}
// This code is contributed by Shrikant13
Output:
The largest connected component of the grid is :9
. . . . . . . .
. 1 1 . . . . .
. . 1 1 . . . .
. . . 1 . . . .
. . . 1 1 . . .
. . . 1 1 . . .
版权属于：月萌API www.moonapi.com，转载请注明出处
