Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <stdio.h>
- #include <stdlib.h>
- int n;
- int **table;
- void dfs(int start_y, int start_x)
- {
- table[start_y][start_x] = 1;
- if ((start_x > 0) && (table[start_y][start_x - 1] == 0)) // <--
- dfs(start_y, start_x - 1); // |
- if ((start_y > 0) && (table[start_y - 1][start_x] == 0))// \|/
- dfs(start_y - 1, start_x);
- if ((start_y < n - 1) && (table[start_y + 1][start_x] == 0))// /|\
- dfs(start_y + 1, start_x); // |
- if ((start_x < n - 1) && (table[start_y][start_x + 1] == 0))// -->
- dfs(start_y, start_x + 1);
- }
- /*
- void print_dzebug()
- {
- printf("\n");
- int i, j;
- for (i = 0; i < n; i++)
- {
- for (j = 0; j < n; j++)
- if (table[i][j] == 1)
- printf("*");
- else printf(" ");
- printf("\n");
- }
- }
- */
- int main()
- {
- int i, j, counter;
- char temp;
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- scanf("%d\n", &n);
- table = (int**)malloc(n * sizeof(int*));
- for (i = 0; i < n; i++)
- table[i] = (int*)calloc(n, sizeof(int));
- for (i = 0; i < n; i++)
- {
- for (j = 0; j < n; j++)
- {
- scanf("%c", &temp);
- if (temp == '*')
- table[i][j] = 1;
- }
- scanf("%c", &temp); // '\n' perenos stroki
- }
- //print_dzebug();
- for (i = 0; i<n; i++) //ishem vhod v verhnei stroke
- if (table[0][i] == 0) // table[y][x]
- {
- dfs(0, i); //zalivaem pustoe prostranstvo
- break;
- }
- //print_dzebug();
- counter = 0;
- for (i = 0; i<n; i++)
- for (j = 0; j < n; j++)
- if (table[i][j] == 0)
- {
- counter++; //kolichestvo nedostezhimih prostranstv
- dfs(i, j); //ishem pustoe prostranstvo i zalivaem
- //print_dzebug();
- }
- printf("%d", counter);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement