Advertisement
Guest User

Untitled

a guest
Mar 24th, 2018
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.66 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. int n;
  6. int **table;
  7.  
  8. void dfs(int start_y, int start_x)
  9. {
  10. table[start_y][start_x] = 1;
  11. if ((start_x > 0) && (table[start_y][start_x - 1] == 0)) // <--
  12. dfs(start_y, start_x - 1); // |
  13. if ((start_y > 0) && (table[start_y - 1][start_x] == 0))// \|/
  14. dfs(start_y - 1, start_x);
  15. if ((start_y < n - 1) && (table[start_y + 1][start_x] == 0))// /|\
  16. dfs(start_y + 1, start_x); // |
  17. if ((start_x < n - 1) && (table[start_y][start_x + 1] == 0))// -->
  18. dfs(start_y, start_x + 1);
  19. }
  20. /*
  21. void print_dzebug()
  22. {
  23. printf("\n");
  24. int i, j;
  25. for (i = 0; i < n; i++)
  26. {
  27. for (j = 0; j < n; j++)
  28. if (table[i][j] == 1)
  29. printf("*");
  30. else printf(" ");
  31. printf("\n");
  32. }
  33. }
  34. */
  35.  
  36. int main()
  37. {
  38. int i, j, counter;
  39. char temp;
  40. freopen("input.txt", "r", stdin);
  41. freopen("output.txt", "w", stdout);
  42. scanf("%d\n", &n);
  43. table = (int**)malloc(n * sizeof(int*));
  44. for (i = 0; i < n; i++)
  45. table[i] = (int*)calloc(n, sizeof(int));
  46. for (i = 0; i < n; i++)
  47. {
  48. for (j = 0; j < n; j++)
  49. {
  50. scanf("%c", &temp);
  51. if (temp == '*')
  52. table[i][j] = 1;
  53. }
  54. scanf("%c", &temp); // '\n' perenos stroki
  55. }
  56.  
  57. //print_dzebug();
  58.  
  59. for (i = 0; i<n; i++) //ishem vhod v verhnei stroke
  60. if (table[0][i] == 0) // table[y][x]
  61. {
  62. dfs(0, i); //zalivaem pustoe prostranstvo
  63. break;
  64. }
  65. //print_dzebug();
  66. counter = 0;
  67. for (i = 0; i<n; i++)
  68. for (j = 0; j < n; j++)
  69. if (table[i][j] == 0)
  70. {
  71. counter++; //kolichestvo nedostezhimih prostranstv
  72. dfs(i, j); //ishem pustoe prostranstvo i zalivaem
  73. //print_dzebug();
  74. }
  75. printf("%d", counter);
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement