Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.19 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAXLENGTH 100000
  4. void num_of_islands(int row,int col,int m, int n,char *islands);
  5. int numIslands(char *islands,int row,int col);
  6. void push(int num);
  7. int pop();
  8. int isnull();
  9. char visit(int m,int n,int row,int col,char *islands);
  10.  
  11.  
  12. struct pstack
  13. {
  14.     int top;
  15.     int buf[MAXLENGTH];
  16.  
  17. };
  18.  
  19. struct pstack pstack;
  20. void push(int num)
  21. {
  22.     if (pstack.top >= MAXLENGTH -1)
  23.     {
  24.         printf("stack over");
  25.         return ;
  26.     }
  27.     pstack.buf[pstack.top++] = num;
  28. }
  29. int pop()
  30. {
  31.     if(pstack.top <= 0)
  32.     {
  33.         printf("stack is null");
  34.         return 0;
  35.     }
  36.     --pstack.top;
  37.     return pstack.buf[pstack.top];
  38. }
  39. int isnull()
  40. {
  41.     if (pstack.top == 0)
  42.         return 1;
  43.     else
  44.         return 0;
  45. }
  46.  
  47. int main()
  48. {
  49.     int row,col,i,j;
  50.     pstack.top = 0;
  51.  
  52.     scanf("%d",&row);
  53.     scanf("%d",&col);
  54.     char  *islands = (char *)malloc(sizeof(char) * row * col);
  55.     if(islands == NULL)
  56.         return 0;
  57.     for(i = 0;i < row ;++i)
  58.         for(j = 0;j < col; ++j)
  59.         {
  60.             getchar();
  61.             scanf("%c",&islands[i * col + j]);
  62.         }
  63.     numIslands(islands,row,col);
  64.     free(islands);
  65. }
  66. int numIslands(char *islands,int row,int col)
  67. {
  68.     int i,j;
  69.     int num = 0;
  70.     for(i = 0;i < row ;++i)
  71.         for(j = 0;j < col; ++j)
  72.         {
  73.             if( visit(i,j,row,col,islands)== '1')
  74.             {
  75.                 num_of_islands(row,col,i,j,islands);
  76.                 ++num;
  77.             }
  78.  
  79.         }
  80.     printf("%d",num) ;
  81.     return num;
  82. }
  83.  
  84.  
  85.  
  86. void num_of_islands(int row,int col,int m, int n,char *islands)
  87. {
  88.     int location;
  89.     islands[m * col + n] = '2';
  90.     if(visit(m-1,n,row,col,islands)=='1')
  91.        {
  92.            islands[(m - 1)* col + n] == '2';
  93.            push ((m - 1)* col + n);
  94.        }
  95.     if(visit(m,n-1,row,col,islands)=='1')
  96.         {
  97.             islands[m * col + n - 1] == '2';
  98.             push(m * col + n - 1);
  99.         }
  100.     if(visit(m+1,n,row,col,islands)=='1')
  101.     {
  102.  
  103.         islands[(m + 1)* col + n] == '2';
  104.         push((m + 1)* col + n);
  105.     }
  106.     if(visit(m,n+1,row,col,islands)=='1')
  107.     {
  108.         islands[m * col + n + 1] == '2';
  109.         push(m * col + n + 1);
  110.     }
  111.     while(!isnull())
  112.     {
  113.         location = pop();
  114.         m = location/col;
  115.         n = location % col;
  116.         islands[location] = '0';
  117.  
  118.  
  119.         if(visit(m-1,n,row,col,islands)=='1')
  120.            {
  121.                islands[(m - 1)* col + n] == '2';
  122.                push ((m - 1)* col + n);
  123.            }
  124.         if(visit(m,n-1,row,col,islands)=='1')
  125.             {
  126.                 islands[m * col + n - 1] == '2';
  127.                 push(m * col + n - 1);
  128.             }
  129.         if(visit(m+1,n,row,col,islands)=='1')
  130.         {
  131.  
  132.             islands[(m + 1)* col + n] == '2';
  133.             push((m + 1)* col + n);
  134.         }
  135.         if(visit(m,n+1,row,col,islands)=='1')
  136.         {
  137.             islands[m * col + n + 1] == '2';
  138.             push(m * col + n + 1);
  139.         }
  140.     }
  141. }
  142.  
  143. char visit(int m,int n,int row,int col,char *islands)
  144. {
  145.     if(m < 0 || n < 0 || m >= row || n >= col)
  146.         return 0;
  147.     else
  148.         return islands[m * col + n];
  149.  
  150. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement