fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #define MAX 100
  4. #define initial 1
  5. #define visited 2
  6. int a[MAX][MAX];
  7. //int state[MAX][MAX];
  8. int n;
  9. int value[5];
  10. void set_to_initial(int state[n][n])
  11. {
  12.  int i,j;
  13.  for(i=0;i<n;i++)
  14.  for(j=0;j<n;j++)
  15.  {
  16.  state[i][j]=initial;
  17.  }
  18. }
  19. void BFS(int k,int i,int j,int state[n][n])
  20. {
  21.  state[i][j]=visited;
  22.  if(i>0)
  23.  if(a[i-1][j]==k&&state[i-1][j]==initial)
  24.  BFS(k,i-1,j,state);
  25.  if(j>0)
  26.  if(a[i][j-1]==k&&state[i][j-1]==initial)
  27.  BFS(k,i,j-1,state);
  28.  if(j<n-1)
  29.  if(a[i][j+1]==k&&state[i][j+1]==initial)
  30.  BFS(k,i,j+1,state);
  31.  if(i<n-1)
  32.  if(a[i+1][j]==k&&state[i+1][j]==initial)
  33.  BFS(k,i+1,j,state);
  34. }
  35. void BFS2(int i,int j,int state[n][n])
  36. {
  37.  state[i][j]=visited;
  38.  if(i>0)
  39.  if(a[i-1][j]==0&&state[i-1][j]==initial)
  40.  BFS2(i-1,j,state);
  41.  else if(a[i-1][j]!=0&&state[i-1][j]==initial)
  42.  BFS(a[i-1][j],i-1,j,state);
  43.  if(j>0)
  44.  if(a[i][j-1]==0&&state[i][j-1]==initial)
  45.  BFS2(i,j-1,state);
  46.  else if(a[i][j-1]!=0&&state[i][j-1]==initial)
  47.  BFS(a[i][j-1],i,j-1,state);
  48.  if(j<n-1)
  49.  if(a[i][j+1]==0&&state[i][j+1]==initial)
  50.  BFS2(i,j+1,state);
  51.  else if(a[i][j+1]!=0&&state[i][j+1]==initial)
  52.  BFS(a[i][j+1],i,j+1,state);
  53.  if(i<n-1)
  54.  if(a[i+1][j]==0&&state[i+1][j]==initial)
  55.  BFS2(i+1,j,state);
  56.  else if(a[i+1][j]!=0&&state[i+1][j]==initial)
  57.  BFS(a[i+1][j],i+1,j,state);
  58. }
  59. int countArea(int state[n][n])
  60. {
  61.  int i,j,k;
  62.  for(i=0;i<n;i++)
  63.  for(j=0;j<n;j++)
  64.  if(a[i][j]!=0&&state[i][j]==visited)
  65.  for(k=0;k<5;k++)
  66.  if(a[i][j]==k+1)
  67.  value[k]=value[k]+1;
  68.  int x=1;
  69.  int max=value[0];
  70.  for(i=1;i<5;i++)
  71.  {
  72.  if(value[i]>=max)
  73.  {
  74.  max=value[i];
  75.  x=i+1;
  76.  }
  77.  }
  78.  for(i=0;i<5;i++)
  79.  value[i]=0;
  80.  //printf("%d\n",x);
  81.  return x;
  82. }
  83. void initialize(int state[n][n])
  84. {
  85.  int i,j;
  86.  for(i=0;i<n;i++)
  87.  for(j=0;j<n;j++)
  88.  if(a[i][j]!=0)
  89.  state[i][j]=initial;
  90. }
  91. void setValue(int x,int state[n][n])
  92. {
  93.  int i,j;
  94.  for(i=0;i<n;i++)
  95.  {
  96.  for(j=0;j<n;j++)
  97.  {
  98.  if(a[i][j]==0&&state[i][j]==visited)
  99.  a[i][j]=x;
  100.  }
  101.  }
  102. }
  103. main()
  104. {
  105.  int T,i,j,k,count,tot,countZero,flag;
  106.  scanf("%d",&T);
  107.  for(int t=1;t<=T;t++)
  108.  {
  109.  count=0;
  110.  tot=0;
  111.  countZero=0;
  112.  flag=0;
  113.  scanf("%d",&n);
  114.  if(n<4||n>100)
  115.  {
  116.  break;
  117.  }
  118.  for(i=0;i<n;i++)
  119.  {
  120.  for(j=0;j<n;j++)
  121.  {
  122.  scanf("%d",&a[i][j]);
  123.  if(a[i][j]<0||a[i][j]>5)
  124.  {
  125.  flag=1;
  126.  break;
  127.  }
  128.  }
  129.  if(flag==1)
  130.  break;
  131.  }
  132.  if(flag==1)
  133.  break;
  134.  int state[n][n];
  135.  set_to_initial(state);
  136.  int abcd[n*n];
  137.  for(i=0;i<n;i++)
  138.  {
  139.  for(j=0;j<n;j++)
  140.  {
  141.  if(a[i][j]==0&&state[i][j]==initial)
  142.  {
  143.  BFS2(i,j,state);
  144.  countZero++;
  145.  abcd[countZero]=countArea(state);
  146.  initialize(state);
  147.  }
  148.  }
  149.  }
  150.  //printf("%d\n",countZero);
  151.  countZero=0;
  152.  set_to_initial(state);
  153.  for(i=0;i<n;i++)
  154.  {
  155.  for(j=0;j<n;j++)
  156.  {
  157.  if(a[i][j]==0&&state[i][j]==initial)
  158.  {
  159.  BFS(0,i,j,state);
  160.  countZero++;
  161.  setValue(abcd[countZero],state);
  162.  }
  163.  }
  164.  }
  165.  for(i=0;i<n;i++)
  166.  {
  167.  for(j=0;j<n;j++)
  168.  printf("%d ",a[i][j]);
  169.  printf("\n");
  170.  }
  171.  set_to_initial(state);
  172.  for(k=1;k<=n;k++)
  173.  { count=0;
  174.  for(i=0;i<n;i++)
  175.  for(j=0;j<n;j++)
  176.  if(a[i][j]==k&&state[i][j]==initial)
  177.  {
  178.  BFS(k,i,j,state);
  179.  count++;
  180.  }
  181.  //printf("\n#%d %d\n",k,count);
  182.  tot+=count;
  183.  }
  184.  printf("#%d %d",t,tot);
  185.  }
  186. }
Success #stdin #stdout 0s 2204KB
comments (?)
stdin
copy 
2
5
5 5 1 4 4
4 0 2 4 2
5 0 0 2 0
5 4 3 0 1
1 3 3 2 1
7
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
5 0 5 0 5 0 5
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
stdout
copy 
5 5 1 4 4 
4 5 2 4 2 
5 5 5 2 2 
5 4 3 3 1 
1 3 3 2 1 
#1 115 5 5 5 5 5 5 
5 5 5 5 5 5 5 
5 5 5 5 5 5 5 
5 5 5 5 5 5 5 
5 5 5 5 5 5 5 
5 5 5 5 5 5 5 
5 5 5 5 5 5 5 
#2 1
https://ideone.com/6Sf7Ua
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!