PROBLEM LINK
Problem Setter : Rishika Ghosh
Tester : Srinjoy Ray
Editorialist: Kanisht Agarwal
DIFFICULTY
Easy
PREREQUISITES:
Basic observations, DFS on 2-D grid.
PROBLEM:
Given an N x M grid A consisting of 0’s and 1’s , where the 1’s represent a block of a house and 0’s are non-residential places.You are required to print the top left and bottom right coordinates of the houses in the grid. And it’s guaranteed that all the houses in the grid are rectangular or square in shape.
EXPLANATION
The given problem is just a variation of a standard graph problem : - Counting of Islands in a 2-D grid using DFS. Here the houses in the grid are analogous to the islands.
So we just need to traverse the houses by using DFS on 2-D grid.
The houses (islands) are basically the connected components of the graph. To get the coordinates of the top-left and bottom-right corner of the house we just need to traverse linearly until and unless we reach a ‘0’ or a non-residential place.
The complexity of DFS on 2-D grid of dimensions N x M is O(MN).
Space complexity : O(MN)
Video Tutorial for counting of connected components in a 2-D grid (Link).
Problem for practice : link
SOLUTIONS :
Setter's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<int>> findSantasMap(vector<vector<int>> &grid) {
int n=grid.size();
int m=grid[0].size();
vector<vector<int>> ans;
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
if (grid[i][j]==1 && (i-1<0 || grid[i - 1][j]==0) &&
(j-1<0 || grid[i][j - 1]==0)) {
// top left
int x1 = i;
int y1 = j;
int x2 = i;
int y2 = j;
// update bottom right: find 1
while (x2<n && grid[x2][j] == 1) {
x2++;
}
// now x2 stop at 0 ele or out of boudary
x2--;
while (y2<m && grid[i][y2] == 1) {
y2++;
}
y2--;
ans.push_back({x1, y1, x2, y2});
}
}
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
vector<vector<int>> grid(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>grid[i][j];
}
}
vector<vector<int>> ans=findSantasMap(grid);
if(ans.empty()){
cout<<-1<<'\n';
continue;
}
cout<<ans.size()<<'\n';
for(int i=0;i<ans.size();i++){
for(int j=0;j<ans[0].size();j++){
cout<<ans[i][j]<<" ";
}
cout<<'\n';
}
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int mat[N][N],vis[N][N];
void solve(){
int i,j,i1,j1,end_i,end_j;
int n,m;
cin>>n>>m;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cin>>mat[i][j];
vis[i][j]=0;
}
}
vector<vector<int>> ans;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(mat[i][j]==0 || vis[i][j]==1){
continue;
}
end_i = i;
while(end_i<n && mat[end_i][j]==1){
end_i++;
}
end_i--;
end_j = j;
while(end_j<m && mat[end_i][end_j]==1){
end_j++;
}
end_j--;
for(i1=i;i1<=end_i;i1++){
for(j1=j;j1<=end_j;j1++){
vis[i1][j1]=1;
}
}
ans.push_back({i,j,end_i,end_j});
}
}
if(ans.size()==0){
cout<<"-1\n";
return;
}
cout<<ans.size()<<'\n';
for(i=0;i<ans.size();i++){
for(int j=0;j<ans[i].size();j++){
cout<<ans[i][j];
if(j!=ans[i].size()-1){
cout<<" ";
}
else{
cout<<'\n';
}
}
}
}
int main(){
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
}
Editorialist's Solution
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
using namespace std;
int dx[8] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};
int a[1001][1001];
int vis[1001][1001];
int n, m;
bool isvalid(int x, int y)
{
if (x > n || x < 1 || y > m || y < 1 )
return false;
if (vis[x][y] || !a[x][y])
return false;
return true;
}
void dfs(int x, int y)
{
vis[x][y] = 1;
for (int i = 0; i < 4; i++)
{
if (isvalid(x + dx[i], y + dy[i]))
{
dfs(x + dx[i], y + dy[i]);
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
t = 1;
cin >> t;
while (t--)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
vis[i][j] = 0;
a[i][i] = 0;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
vector<pair<pair<int, int>, pair<int, int>>>ans;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (!vis[i][j] && a[i][j])
{
dfs(i, j);
int fini = i;
int finj = j;
while (fini <= n && a[fini][j] == 1)
fini++;
while (finj <= m && a[i][finj] == 1)
finj++;
ans.pb({{i, j}, {fini - 1, finj - 1}});
}
}
}
if (ans.size())
{
cout << ans.size() << "\n";
for (auto i : ans)
{
cout << i.ff.ff - 1 << " " << i.ff.ss - 1 << " " << i.ss.ff - 1 << " " << i.ss.ss - 1 << "\n";
}
}
else
{
cout << "-1\n";
}
}
return 0;
}