Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #define MAXLENGTH 100000
- void num_of_islands(int row,int col,int m, int n,char *islands);
- int numIslands(char *islands,int row,int col);
- void push(int num);
- int pop();
- int isnull();
- char visit(int m,int n,int row,int col,char *islands);
- struct pstack
- {
- int top;
- int buf[MAXLENGTH];
- };
- struct pstack pstack;
- void push(int num)
- {
- if (pstack.top >= MAXLENGTH -1)
- {
- printf("stack over");
- return ;
- }
- pstack.buf[pstack.top++] = num;
- }
- int pop()
- {
- if(pstack.top <= 0)
- {
- printf("stack is null");
- return 0;
- }
- --pstack.top;
- return pstack.buf[pstack.top];
- }
- int isnull()
- {
- if (pstack.top == 0)
- return 1;
- else
- return 0;
- }
- int main()
- {
- int row,col,i,j;
- pstack.top = 0;
- scanf("%d",&row);
- scanf("%d",&col);
- char *islands = (char *)malloc(sizeof(char) * row * col);
- if(islands == NULL)
- return 0;
- for(i = 0;i < row ;++i)
- for(j = 0;j < col; ++j)
- {
- getchar();
- scanf("%c",&islands[i * col + j]);
- }
- numIslands(islands,row,col);
- free(islands);
- }
- int numIslands(char *islands,int row,int col)
- {
- int i,j;
- int num = 0;
- for(i = 0;i < row ;++i)
- for(j = 0;j < col; ++j)
- {
- if( visit(i,j,row,col,islands)== '1')
- {
- num_of_islands(row,col,i,j,islands);
- ++num;
- }
- }
- printf("%d",num) ;
- return num;
- }
- void num_of_islands(int row,int col,int m, int n,char *islands)
- {
- int location;
- islands[m * col + n] = '2';
- if(visit(m-1,n,row,col,islands)=='1')
- {
- islands[(m - 1)* col + n] == '2';
- push ((m - 1)* col + n);
- }
- if(visit(m,n-1,row,col,islands)=='1')
- {
- islands[m * col + n - 1] == '2';
- push(m * col + n - 1);
- }
- if(visit(m+1,n,row,col,islands)=='1')
- {
- islands[(m + 1)* col + n] == '2';
- push((m + 1)* col + n);
- }
- if(visit(m,n+1,row,col,islands)=='1')
- {
- islands[m * col + n + 1] == '2';
- push(m * col + n + 1);
- }
- while(!isnull())
- {
- location = pop();
- m = location/col;
- n = location % col;
- islands[location] = '0';
- if(visit(m-1,n,row,col,islands)=='1')
- {
- islands[(m - 1)* col + n] == '2';
- push ((m - 1)* col + n);
- }
- if(visit(m,n-1,row,col,islands)=='1')
- {
- islands[m * col + n - 1] == '2';
- push(m * col + n - 1);
- }
- if(visit(m+1,n,row,col,islands)=='1')
- {
- islands[(m + 1)* col + n] == '2';
- push((m + 1)* col + n);
- }
- if(visit(m,n+1,row,col,islands)=='1')
- {
- islands[m * col + n + 1] == '2';
- push(m * col + n + 1);
- }
- }
- }
- char visit(int m,int n,int row,int col,char *islands)
- {
- if(m < 0 || n < 0 || m >= row || n >= col)
- return 0;
- else
- return islands[m * col + n];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement