fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 201;
  5.  
  6. int n, m;
  7. string todo;
  8. string moves;
  9. string s[MAX];
  10. int row[MAX], col[MAX];
  11. int _row[MAX], _col[MAX];
  12.  
  13. void transpose_row(bool rev) {
  14.   fill(_row, _row + n, 0);
  15.   for(int j = 0; j < m; ++j) {
  16.     _row[0] += 1;
  17.     _row[col[j]] -= 1;
  18.   }
  19.   row[0] = _row[0];
  20.   for(int i = 1; i < n; ++i) {
  21.     _row[i] += _row[i-1];
  22.     row[i] = _row[i];
  23.   }
  24.   if (rev) {
  25.     for(int i = 0; i < n/2; ++i) {
  26.       swap(row[i], row[n-i-1]);
  27.     }
  28.   }
  29. }
  30.  
  31. void transpose_col(bool rev) {
  32.   fill(_col, _col + m, 0);
  33.   for(int i = 0; i < n; ++i) {
  34.     _col[0] += 1;
  35.     _col[row[i]] -= 1;
  36.   }
  37.   col[0] = _col[0];
  38.   for(int j = 1; j < m; ++j) {
  39.     _col[j] += _col[j-1];
  40.     col[j] = _col[j];
  41.   }
  42.   if (rev) {
  43.     for(int j = 0; j < m/2; ++j) {
  44.       swap(col[j], col[m-j-1]);
  45.     }
  46.   }
  47. }
  48.  
  49. void move_up() {
  50.   for(int j = 0; j < m; ++j) {
  51.     for(int i = 0; i < col[j]; ++i) {
  52.       s[i][j] = '1';
  53.     }
  54.     for(int i = col[j]; i < n; ++i) {
  55.       s[i][j] = '0';
  56.     }
  57.   }
  58. }
  59.  
  60. void move_down() {
  61.   for(int j = 0; j < m; ++j) {
  62.     for(int i = n-1; i >= n-col[j]; --i) {
  63.       s[i][j] = '1';
  64.     }
  65.     for(int i = n-col[j]-1; i >= 0; --i) {
  66.       s[i][j] = '0';
  67.     }
  68.   }
  69. }
  70.  
  71. void move_left() {
  72.   for(int i = 0; i < n; ++i) {
  73.     for(int j = 0; j < row[i]; ++j) {
  74.       s[i][j] = '1';
  75.     }
  76.     for(int j = row[i]; j < m; ++j) {
  77.       s[i][j] = '0';
  78.     }
  79.   }
  80. }
  81.  
  82. void move_right() {
  83.   for(int i = 0; i < n; ++i) {
  84.     for(int j = m-1; j >= m-row[i]; --j) {
  85.       s[i][j] = '1';
  86.     }
  87.     for(int j = m-row[i]-1; j >= 0; --j) {
  88.       s[i][j] = '0';
  89.     }
  90.   }
  91. }
  92.  
  93. string compress(string &s) {
  94.   string x = "";
  95.   for(int i = 0; i < s.length(); ++i) {
  96.     int j = i;
  97.     while(s[i] == s[j] && j < s.length()) {
  98.       ++j;
  99.     }
  100.     x += s[i];
  101.     i = j - 1;
  102.   }
  103.   return x;
  104. }
  105.  
  106. void apply(int i) {
  107.   todo += moves[i];
  108.   if (moves[i] == 'L') {
  109.     transpose_col(0);
  110.   }
  111.   else if (moves[i] == 'R') {
  112.     transpose_col(1);
  113.   }
  114.   else if (moves[i] == 'D') {
  115.     transpose_row(1);
  116.   }
  117.   else {
  118.     transpose_row(0);
  119.   }
  120. }
  121.  
  122. int main() {
  123.   ios_base::sync_with_stdio(false);
  124.   int t;
  125.   cin >> t;
  126.   while(t--) {
  127.     cin >> n >> m;
  128.     for(int i = 0; i < n; ++i) {
  129.       cin >> s[i];
  130.     }
  131.     for(int i = 0; i < n; ++i) {
  132.       row[i] = 0;
  133.       for(int j = 0; j < m; ++j) {
  134.         row[i] += s[i][j] - '0';
  135.       }
  136.     }
  137.     for(int j = 0; j < m; ++j) {
  138.       col[j] = 0;
  139.       for(int i = 0; i < n; ++i) {
  140.         col[j] += s[i][j] - '0';
  141.       }
  142.     }
  143.     todo.clear();
  144.     cin >> moves;
  145.     moves = compress(moves);
  146.     for(int i = 0; i < moves.length(); ++i) {
  147.       int j = i;
  148.       while(j < moves.length()) {
  149.         if ((moves[i] == 'L' || moves[i] == 'R') &&
  150.             (moves[j] == 'L' || moves[j] == 'R')) {
  151.           j += 1;
  152.         }
  153.         else if ((moves[i] == 'U' || moves[i] == 'D') &&
  154.             (moves[j] == 'U' || moves[j] == 'D')) {
  155.           j += 1;
  156.         }
  157.         else {
  158.           apply(j-1);
  159.           i = j - 1;
  160.           break;
  161.         }
  162.       }
  163.     }
  164.     apply(moves.length()-1);
  165.     for(int i = max(0, (int)todo.length()-2); i < todo.length(); ++i) {
  166.       if (todo[i] == 'L') {
  167.         move_left();
  168.       }
  169.       else if (todo[i] == 'R') {
  170.         move_right();
  171.       }
  172.       else if (todo[i] == 'D') {
  173.         move_down();
  174.       }
  175.       else {
  176.         move_up();
  177.       }
  178.     }
  179.     for(int i = 0; i < n; ++i) {
  180.       cout << s[i] << "\n";
  181.     }
  182.   }
  183.   return 0;
  184. }
Success #stdin #stdout 0s 4316KB
comments (?)
stdin
copy 
4
4 4
1010
0010
1001
0100
ULRDU
4 4
1010
0010
1001
0100
LRDU
4 3
000
010
001
101
LRL
3 2
01
10
00
D
stdout
copy 
1111
0011
0000
0000
0011
0011
0001
0001
000
100
100
110
00
00
11
https://ideone.com/cGWojA
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!