Найти наибольшую область в массиве 2d в переполнении стека
Мне нужно написать рекурсивную функцию в C ++, которая находит наибольшую область числа ‘1’ в 2d массиве, который содержит только 1 или 0.
Пример:
int Arr[5][8] =
{
{ 0, 0, 0, 0, 1, 1, 0, 0, },
{ 1, 0, 0, 1, 1, 1, 0, 0, },
{ 1, 1, 0, 1, 0, 1, 1, 0, },
{ 0, 0, 0, 1, 1, 1, 1, 0, },
{ 0, 1, 1, 0, 0, 0, 0, 0, },
};
Визуальный пример: http://s23.postimg.org/yabwp6h23/find_largest.png
Самая большая область этого массива — 12, вторая по величине — 3, а третья по величине — 2.
Я думал сделать это с помощью чего-то похожего на алгоритм заливки, но просто не могу понять, как.
Решение
Я думал сделать это с чем-то похожим на алгоритм заливки
Я думаю, что это довольно хороший способ сделать это. Применить заливку к любому 1, считая их и заменяя их нулями.
Повторяйте, пока сетка полностью не состоит из нулей.
Далее будут распечатаны размеры подключенных компонентов в произвольном порядке:
#include <iostream>
constexpr int N = 5;
constexpr int M = 8;
int arr[N][M] =
{
{ 0, 0, 0, 0, 1, 1, 0, 0, },
{ 1, 0, 0, 1, 1, 1, 0, 0, },
{ 1, 1, 0, 1, 0, 1, 1, 0, },
{ 0, 0, 0, 1, 1, 1, 1, 0, },
{ 0, 1, 1, 0, 0, 0, 0, 0, },
};
int fill(int arr[N][M], int r, int c) {
int count = 0;
if (r < N && arr[r][c]) {
for (int i = c; i >= 0 && arr[r][i]; --i) {
arr[r][i] = 0;
count += fill(arr, r + 1, i) + 1;
}
for (int i = c + 1; i < M && arr[r][i]; ++i) {
arr[r][i] = 0;
count += fill(arr, r + 1, i) + 1;
}
}
return count;
}
int print_components(int arr[N][M]) {
for (int r = 0; r < N; ++r) {
for (int c = 0; c < M; ++c) {
if (arr[r][c]) {
std::cout << fill(arr, r, c) << std::endl;
}
}
}
}
int main() {
print_components(arr);
}
Другие решения
bool visited[5][8];
int i,j;
// variables for the area:
int current_area = 0, max_area = 0;
int Arr[5][8]={ // type your map of values here
}
// functions
void prepare_visited_map() {
for(i=0;i<5;i++) {
for(j=0;j<8;j++) visited[i][j] = false;
}
}
// recursive function to calculate the area around (x,y)
void calculate_largest_area(int x, int y) {
if(visited[x][y]) return;
// check if out of boundaries
if(x<0 || y<0 || x>=5 || y>=8) return;
// check if the cell is 0
if(!Arr[x][y]) {
visited[x][y] = true;
return;
}
// found a propper cell, proceed
current_area++;
visited[x][y] = true;
// call recursive function for the adjacent cells (north, east, south, west)
calculate_largest_area(x,y-1);
calculate_largest_area(x+1,y);
calculate_largest_area(x,y+1);
calculate_largest_area(x-1,y);
// by the end of the recursion current_area will hold the area around the initial cell
}
// main procedure where the above functions are used
int mian() {
// calculate the sorrounding area of each cell, and pick up the largest of all results
for(i=0;i<5;i++) {
for(j=0;j<8;j++) {
prepare_visited_map();
calculate_largest_area(i,j);
if(current_area > max_area) max_area = current_area;
}
}
printf("Max area is %d",max_area");
}
Надеюсь, это было полезно 🙂
что-то вроде,
int max_area = 0;
foreach y
foreach x
if (pos[y][x] == 1 && !visited[y][x])
{
int area = 0;
Queue queue = new Queue();
queue.push(new Point(x, y));
visited[y][x] = true;
while (!queue.empty())
{
Point pt = queue.pop();
area++;
foreach neightboor of pt (pt.x±1, pt.y±1)
if (pos[neightboor.y][neightboor.x] == 1 && !visited[neightboor.y][neightboor.x])
{
visited[neightboor.y][neightboor.x] = true;
queue.push(new Point(neightboor.x, neightboor.y));
}
}
if (area > max_area)
max_area = area;
}
Быстрый подход, но я не знаю, есть ли способ сделать это разумным способом (рекурсивно
вызов для каждого элемента не масштабируется для C ++, потому что стек вызовов ограничен)
int maxy = 5
int maxx = 8
int areasize(int x, int y) {
if (x < 0 || y < 0 || x > maxx || y > maxy || !Arr[y][x])
return 0;
Arr[y][x] = 0;
return 1
+ areasize(x + 1, y)
+ areasize(x - 1, y)
+ areasize(x, y + 1)
+ areasize(x, y - 1);
}
maxarea = 0;
for (int y = 0; y < maxy; y++) {
for (int x = 0; x < maxx; x++) {
maxarea = std::max(maxarea, areasize(x, y));
}
}