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
Answers
Answer:
j2 ki set zguajs837 th visit c
Explanation:
j se is hi 2ubeoaj6
Answer:
The program demonstrates in the language of java
Explanation:
import java.util.ArrayList;
import java.util.Map;
import java.util.Random;
class Coord // represents the coordinate system
{
public int x, y;
public Coord(int x, int y)
{
this.x = x;
this.y = y;
}
public String toString(){
return "(" + x + "," + y + ")";
}
}
public class Main {
private static final int ROW = 9;
private static final int COL = 9;
private static int LEFT_TOP = 0;
private static int TOP = 1;
private static int RIGHT_TOP = 2;
private static int RIGHT = 3;
private static int RIGHT_BOTTOM = 4;
private static int BOTTOM = 5;
private static int LEFT_BOTTOM = 6;
private static int LEFT = 7;
private static int DIRECTION_COUNT = 8;
public static void main(String[] args) {
boolean grid[][] = new boolean[ROW][COL];
fill(grid);
print(grid);
ArrayList<Map.Entry<Coord,ArrayList<Coord>>> connectedCities =
getConnectedCities(grid);
printCities(connectedCities);
}
static private void fill(boolean grid[][])
{
final Random rnd = new Random();
for (int r = 0; r < ROW; r++)
for (int c = 0; c < COL; c++)
grid[r][c] = rnd.nextBoolean();
}
static private void print(boolean grid[][])
{
for (int r = 0; r < ROW; r++){
for(int c = 0; c < COL; c++){
System.out.print(grid[r][c] ? "1" : "0");
}
System.out.println();
}
}
static private void printCities(ArrayList<Map.Entry<Coord,ArrayList<Coord>>> connectedCities)
{
if (connectedCities.isEmpty())
{
System.out.println("Connected city is not existing");
return;
}
for (int index = 0; index < connectedCities.size(); index++)
{
Map.Entry<Coord,ArrayList<Coord>> item = connectedCities.get(index);
System.out.print("City " + item.getKey().toString() + " is connected to: ");
ArrayList<Coord> conCities = item.getValue();
for (int idx = 0; idx < conCities.size(); idx++)
System.out.print(conCities.get(idx).toString() + (idx + 1 == conCities.size() ? " " : ", "));
}
}
static private ArrayList<Map.Entry<Coord,ArrayList<Coord>>> getConnectedCities(boolean grid[][])
{
ArrayList<Map.Entry<Coord,ArrayList<Coord>>> cities = new ArrayList<Map.Entry<Coord,ArrayList<Coord>>>();
Coord points[] = new Coord[DIRECTION_COUNT];
for (int rowIndex = 0; rowIndex < ROW; rowIndex++)
{
for (int colIndex = 0; colIndex < COL; colIndex++)
{
if (grid[colIndex][rowIndex]) // if this city is marked
{
points[LEFT] = new Coord(colIndex - 1, rowIndex);
points[LEFT_TOP] = new Coord(colIndex-1, rowIndex-1);
points[TOP] = new Coord( colIndex, rowIndex - 1);
points[RIGHT_TOP] = new Coord(colIndex + 1, rowIndex - 1);
points[RIGHT] = new Coord(colIndex + 1, rowIndex);
points[RIGHT_BOTTOM] = new Coord(colIndex + 1, rowIndex + 1);
points[BOTTOM] = new Coord(colIndex, rowIndex + 1);
points[LEFT_BOTTOM] = new Coord(colIndex -1, rowIndex + 1);
for (int dirIndex = 0; dirIndex < DIRECTION_COUNT; dirIndex++)
{
ArrayList<Coord> conCities = new ArrayList<>();
Coord point = points[dirIndex];
if (isValidCoord(point) && grid[point.y][point.x])
conCities.add(point);
if (!conCities.isEmpty()){
int finalRowIndex = rowIndex;
int finalColIndex = colIndex;
cities.add(new Map.Entry<Coord, ArrayList<Coord>>(){
@Override
public Coord getKey(){
return new Coord(finalColIndex, finalRowIndex);
}
@Override
public ArrayList<Coord> getValue(){
public ArrayList<Coord> setValue(ArrayList<Coord> value){
return null;
} });
}
}
}
}
}
return cities;
w }
static private boolean isValidCoord(Coord c)
{
if (c.x < 0 || c.y < 0)
return false;
if (c.x >= COL || c.y >= ROW )
return false;
return true;
}
}