fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. class simulator {
  8. public:
  9. simulator(const vector<string> &board) {
  10. if (board.size() < 3) {
  11. throw invalid_argument("invalid board height");
  12. }
  13. if (board[0].size() < 3) {
  14. throw invalid_argument("invalid board width");
  15. }
  16. for (auto &row : board) {
  17. if (row.size() != board[0].size()) {
  18. throw invalid_argument("inconsistent board width");
  19. }
  20. vector<int> t;
  21. for (char ch : row) {
  22. if (ch == 'W') {
  23. t.push_back(0);
  24. }
  25. else if (ch == 'R') {
  26. t.push_back(1);
  27. }
  28. else {
  29. throw invalid_argument("invalid element");
  30. }
  31. }
  32. b.push_back(t);
  33. }
  34. x = -1;
  35. y = height() - 1;
  36. c = -1;
  37. }
  38.  
  39. int height() const {
  40. return b.size();
  41. }
  42.  
  43. int width() const {
  44. return b[0].size();
  45. }
  46.  
  47. string history() const {
  48. return h;
  49. }
  50.  
  51. bool red() const {
  52. return c == 1;
  53. }
  54.  
  55. void move(const string &dirs, unsigned int repeat = 1) {
  56. while (repeat--) {
  57. for (auto d : dirs) {
  58. move(d);
  59. }
  60. }
  61. }
  62.  
  63. private:
  64. void move(char d) {
  65. switch (d) {
  66. case 'L': --x; break;
  67. case 'R': ++x; break;
  68. case 'U': --y; break;
  69. case 'D': ++y; break;
  70. default: throw invalid_argument("invalid direction");
  71. }
  72. c = b.at(y).at(x) = (b.at(y).at(x) + 1) % 2;
  73. h += d;
  74. }
  75.  
  76. vector<vector<int>> b;
  77. int x, y, c;
  78. string h;
  79. };
  80.  
  81. void sub(simulator &s) {
  82. for (int i = 0; i < s.width() - 1; ++i) {
  83. if (s.red()) {
  84. s.move("RDLU");
  85. }
  86. s.move("R");
  87. }
  88. if (s.red()) {
  89. s.move("DLLURDLURR");
  90. }
  91. s.move("D");
  92. }
  93.  
  94. string solve(const vector<string> &board) {
  95. simulator s(board);
  96.  
  97. s.move("R");
  98. s.move("U", s.height() - 1);
  99. for (int i = 0; i < s.height() - 2; ++i) {
  100. sub(s);
  101. s.move("D");
  102. s.move("L", s.width() - 1);
  103. s.move("U");
  104. }
  105. sub(s);
  106.  
  107. for (int i = 0; i < s.width() - 1; ++i) {
  108. if (s.red()) {
  109. s.move("LUURDLURDD");
  110. }
  111. s.move("L");
  112. }
  113.  
  114. if (s.red()) {
  115. s.move("URDLURD");
  116. }
  117.  
  118. return s.history();
  119. }
  120.  
  121. int main() {
  122. for (int h; (cin >> h) && (h >= 3); ) {
  123. vector<string> board(h);
  124. for (auto &s : board) {
  125. cin >> s;
  126. }
  127. string path = solve(board);
  128. for (auto &s : board) {
  129. cout << s << endl;
  130. }
  131. cout << "=> " << path.size() << " " << path << endl;
  132. }
  133. }
  134.  
Success #stdin #stdout 0s 15248KB
stdin
3
WWW
WWW
WWW
4
RRR
RRR
RRR
RRR
5
RWWWR
WRWWW
RWRWW
RWWRW
WRRWR
10
RWRWRWRWRW
WRWRWRWRWR
RWRWRWRWRW
WRWRWRWRWR
RWRWRWRWRW
WRWRWRWRWR
RWRWRWRWRW
WRWRWRWRWR
RWRWRWRWRW
WRWRWRWRWR
0
stdout
WWW
WWW
WWW
=> 64 RUURDLURRDLLURDLURRDDLLURDLURRDLURDLUURDLURDDLLUURDLURDDLURDLURD
RRR
RRR
RRR
RRR
=> 52 RUUURRDDLLURDLURRDLURDDLLURDLURRDLLURDLURRDLLURDLURD
RWWWR
WRWWW
RWRWW
RWWRW
WRRWR
=> 136 RUUUURRDLURRRDLURDLLURDLURRDDLLLLURRDLURRDLURRDLURDLLURDLURRDDLLLLURRDLURRRDLLURDLURRDDLLLLURRDLURRRDLURDLLURDLURRDLUURDLURDDLLLLURDLURD
RWRWRWRWRW
WRWRWRWRWR
RWRWRWRWRW
WRWRWRWRWR
RWRWRWRWRW
WRWRWRWRWR
RWRWRWRWRW
WRWRWRWRWR
RWRWRWRWRW
WRWRWRWRWR
=> 496 RUUUUUUUUURRDLURRDLURRRRDLURRDLURRRDLLURDLURRDDLLLLLLLLLURRDLURRRDLURRRDLURRRDLURRDDLLLLLLLLLURRDLURRDLURRRRDLURRDLURRRDLLURDLURRDDLLLLLLLLLURDLURRDLURRDLURRDLURRDLURRDLURRDLURRDLURRDLURDDLLLLLLLLLURDLURRDLURRRRDLURRDLURRRRDLURDLLURDLURRDDLLLLLLLLLURRDLURRRDLURRRDLURRRDLURRDDLLLLLLLLLURRDLURRDLURRRRDLURRDLURRRDLLURDLURRDDLLLLLLLLLURDLURRDLURRDLURRDLURRDLURRDLURRDLURRDLURRDLURDDLLLLLLLLLURDLURRDLURRRRDLURRDLURRRRDLURDLLURDLURRDLUURDLURDDLLLUURDLURDDLLLUURDLURDDLLLUURDLURDDLLLUURDLURDDLURDLURD