Question

19. Imagine the field is a 2D plane. Each cell is either water 'W' or a tree 'T. A forest is a collection of connected trees. Two trees are connected if they share a side i.e. if they are adjacent to each other. Your task is, given the information about the field, print the size of the largest forest Size of a forest is the number of trees in it. If there are no forests in the field print -1. Input format: First line contains the size of the matrix N The next N lines contain N characters each, either 'W' or 'T separated by space Read the inputs from the standard input stream Constraints: 1​

Answer 1

Answer:

#include <bits/stdc++.h>

using namespace std;

int main()

{

int n;

cin >> n;

char arr[n][n];

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

cin >> arr[i][j];

}

}

int dx[] = {-1, 0, 1, 0};

int dy[] = {0, -1, 0, 1};

bool visited[n][n];

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

visited[i][j] = false;

}

}

int largest_size = 0;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

if (arr[i][j] == 'T' && visited[i][j] == false)

{

visited[i][j] = true;

queue<pair<int, int>> q;

q.push({i, j});

int size = 0;

while (!q.empty())

{

pair<int, int> p = q.front();

q.pop();

size++;

int x = p.first;

int y = p.second;

for (int k = 0; k < 4; k++)

{

int newx = x + dx[k];

int newy = y + dy[k];

if (newx >= 0 && newx < n && newy >= 0 && newy < n && arr[newx][newy] == 'T' && visited[newx][newy] == false)

{

visited[newx][newy] = true;

q.push({newx, newy});

}

}

}

largest_size = max(largest_size, size);

}

}

}

cout << largest_size << endl;

return 0;

}

#SPJ1