Answer to Question #169834 in C++ for sara

Question

Solve this Backtracking Question in C++

A two dimensional array of characters can be considered as a field. 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. See the sample case for clarity;

Sample Input:

5

TTTWW

TWWTT

TWWTT

TWTTT

WWTTT

Sample Output:

10

Answer 1

    #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;
    }