Advertisement
kostes

Untitled

Nov 13th, 2018
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define FI(_n) for(int i = 0;i<(_n);i++)
  3. #define FJ(_n) for(int j = 0;j<(_n);j++)
  4. #define pb push_back
  5. #define all(c) c.begin(),c.end()
  6. using namespace std;
  7. typedef long long ll;
  8. const ll INF = 1e18 + 1;
  9. #define ndbg 1
  10. int n, m;
  11. char p[101][101];
  12. int ans[101][101];
  13. int cnt = 0;
  14. int func(int x, int y)
  15. {
  16. if(x < 0 || y < 0 || x >= n || y >= m || ans[x][y] != 0 || p[x][y] == 'X') return 9;
  17. int tox, toy, k = 0;
  18.  
  19. tox = x + 2; toy = y + 1;
  20. if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
  21. tox = x + 1; toy = y + 2;
  22. if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
  23. tox = x - 2; toy = y + 1;
  24. if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
  25. tox = x - 1; toy = y + 2;
  26. if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
  27. tox = x + 2; toy = y - 1;
  28. if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
  29. tox = x + 1; toy = y - 2;
  30. if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
  31. tox = x - 2; toy = y - 1;
  32. if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
  33. tox = x - 1; toy = y - 2;
  34. if(tox >= 0 && toy >= 0 && tox < n && toy < m && ans[tox][toy] == 0 && p[tox][toy] != 'X') k++;
  35. return k;
  36. }
  37. void dfs(int x, int y)
  38. {
  39.  
  40. if(x < 0 || x >= n || y < 0 || y >= m) return;
  41. if(ans[x][y] != 0) return;
  42. if(p[x][y] == 'X') return;
  43. cnt++;
  44. ans[x][y] = cnt;
  45. vector< pair<int,pair<int,int> > > s;
  46. s.pb({func(x + 2, y - 1),{x + 2, y - 1}});
  47. s.pb({func(x + 1, y - 2),{x + 1, y - 2}});
  48. s.pb({func(x + 2, y + 1),{x + 2, y + 1}});
  49. s.pb({func(x + 1, y + 2),{x + 1, y + 2}});
  50. s.pb({func(x - 2, y - 1),{x - 2, y - 1}});
  51. s.pb({func(x - 1, y - 2),{x - 1, y - 2}});
  52. s.pb({func(x - 2, y + 1),{x - 2, y + 1}});
  53. s.pb({func(x - 1, y + 2),{x - 1, y + 2}});
  54. random_shuffle(all(s));
  55. sort(all(s));
  56. dfs(s[0].second.first, s[0].second.second);
  57. }
  58. int main()
  59. {
  60. ios_base::sync_with_stdio(0);
  61. #ifdef ndbg
  62. ifstream cin("input.txt");
  63. ofstream cout("output.txt");
  64. #endif
  65. cin.tie(0);cout.tie(0);
  66.  
  67.  
  68. cin >> n >> m;
  69. int sx, sy;
  70. FI(n)
  71. FJ(m)
  72. {
  73. cin>>p[i][j];
  74. if(p[i][j] == 'K') sx = i, sy = j;
  75. }
  76. dfs(sx, sy);
  77. FI(n)
  78. {
  79. FJ(m) cout << ans[i][j]<<" ";
  80. cout<<"\n";
  81. }
  82.  
  83. #ifdef ndbg
  84. cin.close();
  85. cout.close();
  86. #endif
  87. return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement