Guest User

Untitled

a guest
Dec 18th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.08 KB | None | 0 0
  1. # include <iostream>
  2. # include <cstdio>
  3. # include <ctime>
  4. # include <cstdlib>
  5. # include <cmath>
  6. # define for(xxx, yyy, zzz) for(int xxx = yyy; xxx <= zzz; ++xxx)
  7.  
  8. using namespace std;
  9.  
  10. const int MAXN = int(1e2) + 4;
  11. const int INF = int(1e4);
  12. const int MN = int(1e4) + 4;
  13.  
  14. char s[MAXN][MAXN];
  15. short dx[] = {1, -1, 0, 0};
  16. short dy[] = {0, 0, 1, -1};
  17. short qx[MN], qy[MN], qh, qt;
  18. short dp[MAXN][MAXN];
  19. short c[MAXN][MAXN];
  20. int n, m, col = 1;
  21. short aa, bb, cc, dd, Maxans;
  22.  
  23. int main () {
  24.  
  25. // freopen("input.txt", "r", stdin);
  26. // freopen("output.txt", "w", stdout);
  27.  
  28. scanf("%d %d\n", &n, &m);
  29. for (i, 1, n)
  30. for (j, 1, m) {
  31. scanf("%c", &s[i][j]);
  32. if(j == m) scanf("\n");
  33. dp[i][j] = INF;
  34. c[i][j] = 1;
  35. }
  36.  
  37. for (i, 1, n) {
  38. for (j, 1, m) {
  39.  
  40. if(s[i][j] == '#') {
  41. qt = qh = 0;
  42. qh ++;
  43. qx[qh] = i; qy[qh] = j;
  44. dp[i][j] = 0;
  45. }
  46.  
  47. else continue;
  48.  
  49. while (qt < qh) {
  50. qt ++;
  51. short xx = qx[qt], yy = qy[qt];
  52. if(dp[xx][yy] > Maxans) {
  53. if(aa != i)aa = i;
  54. if(bb != j)bb = j;
  55. cc = xx;
  56. dd = yy;
  57. Maxans = dp[xx][yy];
  58. }
  59.  
  60. for (it, 0, 3) {
  61.  
  62. if(xx + dx[it] <= n && xx + dx[it] >= 1 && yy + dy[it] <= m && yy + dy[it] >= 1)
  63. if(s[xx + dx[it]][yy + dy[it]] == '#' && dp[xx][yy] + 1 < dp[xx + dx[it]][yy + dy[it]])
  64. if(c[xx + dx[it]][yy + dy[it]] == col){
  65. qh ++;
  66. qx[qh] = xx + dx[it];
  67. qy[qh] = yy + dy[it];
  68. dp[xx + dx[it]][yy + dy[it]] = dp[xx][yy] + 1;
  69. }
  70. }
  71. c[xx][yy] = col + 1;
  72. dp[xx][yy] = INF;
  73. }
  74.  
  75. col ++;
  76.  
  77. }
  78. }
  79.  
  80. s[aa][bb] = 'X';
  81. s[cc][dd] = 'X';
  82.  
  83. for (i, 1, n) {
  84. for (j, 1, m) {
  85. putchar(s[i][j]);
  86. }
  87. puts("");
  88. }
  89.  
  90. return 0;
  91. }
Add Comment
Please, Sign In to add comment