Question

In: Computer Science

A state is divided into R*C cities.The government has launched an initiative to find the cities...

A state is divided into R*C cities.The government has launched an initiative to find the cities which are dominated by coders. Each city may or may not have coders residing in it. If the city is dominated by coders, it is marked with 1 else it is marked with 0. Two cities are termed as connected cities if they both are dominated by coders and can be reached by moving vertically, horizontally, or diagonally.

Example:

The given is the state with 3*3 cities and their dominance representation.

City[1, 1] is directly connected to City[1, 2].

City[1, 2] is directly connected to City[1, 1], City[1, 3] and City[2, 3].

City[1, 3] is directly connected to City[1, 2] and City[2, 3].

City[2, 3] is directly connected to City[1, 2] and City[1, 3].

City[3, 1] is not connected to any of the other coder dominant cities.

One or more coder dominant connected cities form the Coding belt. In a belt, there may be coder dominant cities which are not directly connected but can be reached by moving through other dominant cities. It is possible that there are multiple coding belts in the state.

Example:

The given is the state with 3*3 cities and their dominance representation.

For the given example, there are two coding belts. C1 represents Coding Belt 1 and C2 represents Coding Belt 2.

The government wants to find the number of coder dominant cities in the largest coding belt.

The government will give you the credits in the initiative. Can you help the government?


Note: For the given example, there are 4 coder dominant cities in the largest coding belt.

Input Format

The first line of input consists of two space-separated integers, number of rows, R, and number of columns, C.

Next R lines each consist of C space-separated integers.


Constraints

1<= R, C <=10

Output Format

Print the number of coder dominant cities in the largest Coding belt.

Sample TestCase 1

Input

5 51 1 1 0 00 1 1 0 00 0 0 0 11 0 0 1 11 1 0 0 1

Output

5

Explanation

There are three belts in the given 5*5 cities.

Coding Belt 1 (C1): Number of Coder Dominant Cities = 5

Coding Belt 2 (C2): Number of Coder Dominant Cities = 4

Coding Belt 3 (C3): Number of Coder Dominant Cities = 3

Solutions

Expert Solution

This question is similar to the problem of finding the number of lands using the dfs approach. Here we just need to find the maximum size of the land. that's why we are using a global variable mx which will be our result

#include<bits/stdc++.h>

using namespace std;

int mx=0;

int r,c;

pair<int,int>moved[]={ {-1,-1}, {-1,0} , {-1,1} , {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1} };

bool issafe(int x,int y)

{

    if(x>=0&&x<r &&y>=0 &&y<c)

    {

        return true;

    }

    return false;

}

void dfs(int i,int j,int &cnt,vector<vector<int>>&adj,vector<vector<bool>>&vis)

{

    vis[i][j]=true;

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

    {

        int n_i=i+moved[k].first;

        int n_j=j+moved[k].second;

        if(issafe(n_i,n_j) && adj[n_i][n_j]==1 && vis[n_i][n_j]==false)

        {

            cnt++;

            dfs(n_i,n_j,cnt,adj,vis);

        }

    }

}

int main()

{

    cin>>r>>c;

    vector<vector<int>>adj(r,vector<int>(c));

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

    {

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

        {

            cin>>adj[i][j];

        }

    }

    vector<vector<bool>>vis(r,vector<bool>(c,false));

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

    {

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

        {

            if(vis[i][j]==false && adj[i][j]==1)

            {

                int cnt=1;

                dfs(i,j,cnt,adj,vis);

                mx=max(mx,cnt);

            }

        }

    }

    cout<<mx<<"\n";

}

Sample output


Related Solutions

A state is divided into R*C cities.The government has launched an initiative to find the cities...
A state is divided into R*C cities.The government has launched an initiative to find the cities which are dominated by coders. Each city may or may not have coders residing in it. If the city is dominated by coders, it is marked with 1 else it is marked with 0. Two cities are termed as connected cities if they both are dominated by coders and can be reached by moving vertically, horizontally, or diagonally. Example: The given is the state...
Any java solution for this question ? A state is divided into R*C cities.The government has...
Any java solution for this question ? A state is divided into R*C cities.The government has launched an initiative to find the cities which are dominated by coders. Each city may or may not have coders residing in it. If the city is dominated by coders, it is marked with 1 else it is marked with 0. Two cities are termed as connected cities if they both are dominated by coders and can be reached by moving vertically, horizontally, or...
What is federalism? Taking the issue of Sanctuary Cities- Should State and Local Government be compelled...
What is federalism? Taking the issue of Sanctuary Cities- Should State and Local Government be compelled comply with Federal Decrees concerning illegal immigration? Remember that immigration that is wholly within the powers of the Federal government by the Constitution. Argue your answer.
Lyft has recently launched “Lyft Scooters” in various cities across the U.S. Imagine the company selects...
Lyft has recently launched “Lyft Scooters” in various cities across the U.S. Imagine the company selects two individuals, Zahra in Madison, Wisconsin, and Mateo in Albuquerque, New Mexico, to test Lyft Scooters in their respective cities. Each recognizes that she or he has a 2% chance of experiencing an accident. If an accident occurs, a $12,000 will be lost due to injury and property damage. What is Zahra’s probability distribution for loss arising out of an accident? What is Zahra’s...
Lyft has recently launched “Lyft Scooters” in various cities across the U.S. Imagine the company selects...
Lyft has recently launched “Lyft Scooters” in various cities across the U.S. Imagine the company selects two individuals, Zahra in Madison, Wisconsin, and Mateo in Albuquerque, New Mexico, to test Lyft Scooters in their respective cities. Each recognizes that she or he has a 2% chance of experiencing an accident. If an accident occurs, a $12,000 will be lost due to injury and property damage. For questions 4-11, assume that Zahra and Mateo decide to pool (or share equally) their...
The Government has recently launched a new and innovative transport system in the country, which is...
The Government has recently launched a new and innovative transport system in the country, which is managed by the Metro Express Co Ltd. The CEO of the company is aware that a big challenge lies ahead in managing a new company and to run it efficiently. The Chairperson of the Board of Directors has stated, at the first meeting, that “Managing an organisation requires various skills and the ability to organise various resources. All these tasks must be executed with...
The Government has recently launched a new and innovative transport system in the country, which is...
The Government has recently launched a new and innovative transport system in the country, which is managed by the Metro Express Co Ltd. The CEO of the company is aware that a big challenge lies ahead in managing a new company and to run it efficiently. The Chairperson of the Board of Directors has stated, at the first meeting, that “Managing an organisation requires various skills and the ability to organise various resources. All these tasks must be executed with...
The Government has recently launched a new and innovative transport system in the country, which is...
The Government has recently launched a new and innovative transport system in the country, which is managed by the Metro Express Co Ltd. The CEO of the company is aware that a big challenge lies ahead in managing a new company and to run it efficiently. The Chairperson of the Board of Directors has stated, at the first meeting, that “Managing an organisation requires various skills and the ability to organise various resources. All these tasks must be executed with...
A particular county in a certain state of a far away country has 17 cities and...
A particular county in a certain state of a far away country has 17 cities and wants to build roads between them to connect them all, that is, there should be a paved path between any two cities. What is the minimum number of roads, each connecting two cities, to guarantee that all cities are connected? Be careful, wrong answers have negative weights.
Robinson has a utility of u(c, r) = cr where c = coconuts and r =...
Robinson has a utility of u(c, r) = cr where c = coconuts and r = leisure. In order to produce coconuts, technology dictates the production, given by c = a(L^1/2) where a = 8, and L = labour. The time constraint is r+L = 12. How many units of labour will be used?
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT