SPOJ #4177. Herding editorial

The question asks for the number of disjoint groups in which the cats can move. For a cat in a square, it always moves in one direction of {North, South, East, West}. It is provided that cats never go outside the city. This information is helpful in building a simple solution using stl in C++.

  • Take the input matrix in an array of strings.
  • Make a map(squares) with each index as key and random value(say 1) as its value. map< pair<int,int>, int > squares. (squares will have N*M elements.)
  • Take an empty array(A) of size N*M. int A[N][M].
  • Take an empty vector(V) and a variable “temp” initialised to 1.
  • Run a loop until the map is not empty.
    • Add a random value(say 1) into vector V.
    • Take the key of first element of map(squares) and run a loop // to trace the path along with given directions.
      • Mark the index in A with value of temp.
      • Erase the element from map having the key as the current index.
      • Find the next index according to the direction given in current index.
      • If next index is already visited and has a value less than temp, remove an element from vector V and come out of loop.
      • If next index is already visited with the same value as temp, just come out of loop.
      • If next index is not visited, continue the loop.
    • Increment value of temp.
  • The size of vector V is the answer.

The reason for why size of vector is the answer? We are incrementing number of groups by 1 whenever we find a new group, by adding an element into the vector. If we find that a group leads to an already traversed group, we are not counting that group by removing an element from the vector.

Coding is left for you. Leave a comment to this post if you have any difficulty in understanding or in coding.

Link to the problem HERDING.

Advertisements

Largest submatrix of all 1’s in a binary matrix

Problem Statement : Given a binary matrix(matrix that have only 1’s and 0’s), find the largest rectangular submatrix that have only 1’s.

Explanation:
We need to construct a matrix of histograms from given matrix. The height of histogram at a cell(H[i][j]) would be number of consecutive 1’s above the current cell along with current cell itself.

Ex: For the binary matrix

0 0 0 0 1
1 1 0 0 1
0 0 1 1 1
0 0 1 1 1
1 1 1 1 1

Histogram matrix would be

0 0 0 0 1
1 1 0 0 2
0 0 1 1 3
0 0 2 2 4
1 1 3 3 5

Now, we need to traverse the matrix and calculate the maximum area possible for each histogram. For this to understand, please refer this page. Observe the graphs shown in the link to understand how to calculate the maximum possible rectangular area in histograms. In our histogram matrix, each row can be considered as a separate histogram and should keep track of maximum area possible for the complete matrix.

Code :

#include <bits/stdc++.h>

using namespace std;

int maxArea(int a[][100],int m,int n)
{
	int area = 0,count,temp;
	/*
	 *Finds maximum area of rectangle from the histograms build.
	*/
	for(int i = 0;i < m;i++)
	{
		for(int j = 0;j < n;j++)
		{
			if(a[i][j] > 0)
			{
				count = a[i][j];
				temp = j-1;
				while(temp >= 0 && a[i][temp] >= a[i][j])
				{
					count+=a[i][j];
					temp--;
				}
				temp = j+1;
				while(temp < n && a[i][temp] >= a[i][j])
				{
					count += a[i][j];
					temp++;
				}
				if(count > area)
					area = count;
			}
		}
	}
    return area;
}

int solve(int a[][100],int m,int n)
{
	int temp = 0;
	/*
	 *Sets a[i][j] to consecutive 1's above it till that cell.
     *It is like building histograms on each row with size of histogram at 
     *an index of a row as number of consecutive 1's till that index.
    */
    for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < m;j++)
		{
			if(a[i][j] == 1)
			{
				if(i >= 1)
					a[i][j] = a[i-1][j] + 1;
				else
					a[i][j] = 1;
			}
		}
	}
    return maxArea(a,m,n);
}

int main()
{
	int m,n;
	scanf("%d %d",&m,&n);
	int a[100][100];
	for(int i = 0;i < m;i++)
	{
		for(int j = 0;j < n;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	printf("%d\n",solve(a,m,n));
	return 0;
}
Ex :
Matrix A[][]

5 5
0 1 0 1 1
0 1 0 0 1
1 1 1 1 1
0 1 1 1 0
0 0 1 0 1

Histogram matrix H[][] will be

0 1 0 1 1
0 2 0 0 2
1 3 1 1 3
0 4 2 2 0
0 0 3 0 1

When calculated for maximum area in histogram, the cells H[3][2] and H[3][3] give count = 6 and is the maximum area over any other cell in matrix H. In the code, I wrote values of histogram matrix in given matrix(A) itself so that no extra space is used to solve the problem.

For any doubts on this topic, comment below.