Skip to content

Instantly share code, notes, and snippets.

@jungrae-prestolabs
Created May 12, 2018 09:23
Show Gist options
  • Save jungrae-prestolabs/40cd4ae8ecae2da23cebf7495f33dc17 to your computer and use it in GitHub Desktop.
Save jungrae-prestolabs/40cd4ae8ecae2da23cebf7495f33dc17 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#define M 59
int n,m,k,s[M][M],chk[M][M],x[4]={-1,1,0,0},y[4]={0,0,1,-1};
void dfs(int a,int b){
chk[a][b]=1;
for (int i=0;i<4;i++) if (s[a+x[i]][b+y[i]] && !chk[a+x[i]][b+y[i]])
dfs(a+x[i], b+y[i]);
}
int main(){
int T; scanf("%d",&T); while(T--) {
int i,j;
scanf("%d %d %d",&n,&m,&k);
for (i=0;i<=n+1;i++) for (j=0;j<=m+1;j++){
s[i][j]=0;
chk[i][j]=0;
}
for (i=1;i<=k;i++){
int a,b;
scanf("%d %d",&a,&b);
s[a+1][b+1]=1;
}
int cnt=0;
for (i=1;i<=n;i++) for (j=1;j<=m;j++) if (s[i][j] && !chk[i][j]){
dfs(i,j);
cnt++;
}
printf("%d\n",cnt);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment