Skip to content

Instantly share code, notes, and snippets.

@Sahil624
Created November 2, 2017 04:31
Show Gist options
  • Save Sahil624/32110ae5f81a038162b81a6ab5aeb643 to your computer and use it in GitHub Desktop.
Save Sahil624/32110ae5f81a038162b81a6ab5aeb643 to your computer and use it in GitHub Desktop.
#include<stdio.h>
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int **arr,int i,int j,int rows,int cols,int **m,int *count)
{
int x,y;
arr[i][j]=1;
if(m[i][j]==0)
return;
*count=*count+1;
for(int k=0;k<4;k++)
{
x=i+dir[k][0];
y=j+dir[k][1];
if(x<rows && y<cols && x>=0 && y>=0)
{
if(arr[x][y]!=1)
{
dfs(arr,x,y,rows,cols,m,count);
}
}
}
}
int* countGroups(int rows, int cols, int** m, int t_size, int* t, int* result_size) {
*result_size=t_size;
int *res=(int *)malloc(sizeof(int)*(*result_size));
for(int i=0;i<t_size;i++)
res[i]=0;
int **arr;
arr=(int **)malloc(sizeof(int *)*rows);
for(int i=0;i<rows;i++)
arr[i]=(int *)malloc(sizeof(int)*cols);
for(int i=0;i<rows;i++)
for(int j=0;j<cols;j++)
arr[i][j]=0;
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(arr[i][j]==0)
{
int count=0;
dfs(arr,i,j,rows,cols,m,&count);
for(int z=0;z<t_size;z++)
{
if(count==t[z])
{
res[z]=res[z]+1;
}
}
}
}
}
return res;
}
int main()
{
FILE *f = stdout;
char *output_path = getenv("OUTPUT_PATH");
if (output_path) {
f = fopen(output_path, "w");
}
int* res;
int res_size;
int m_rows = 0;
int m_cols = 0;
scanf("%d", &m_rows);
scanf("%d", &m_cols);
int** m = (int**)malloc(m_rows*sizeof(int*));
int m_init_i = 0;
for (m_init_i = 0; m_init_i < m_rows; ++m_init_i) {
m[m_init_i] = (int*)malloc(m_cols*(sizeof(int)));
}
int m_i, m_j;
for (m_i = 0; m_i < m_rows; m_i++) {
for (m_j = 0; m_j < m_cols; m_j++) {
int m_item;
scanf("%d", &m_item);
m[m_i][m_j] = m_item;
}
}
int t_size = 0;
scanf("%d\n", &t_size);
int t[t_size];
for(int i = 0; i < t_size; i++) {
int t_item;
scanf("%d", &t_item);
t[i] = t_item;
}
res = countGroups(m_rows, m_cols, m, t_size, t, &res_size);
for (int res_i = 0; res_i < res_size; res_i++) {
fprintf(f, "%d\n", res[res_i]);
}
fclose(f);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment