fork(1) download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std; 
  4.  
  5. #define All(A) (A).begin(), (A).end()
  6. #define SZ(A) int((A).size())
  7. #define pr_q priority_queue
  8. #define pb push_back
  9. #define mp make_pair
  10. #define INF (1<<30)
  11. #define sc second
  12. #define fr first
  13.  
  14.  
  15. const long double PI = 3.1415926535897932384633832795;
  16. const double EPS = 1e-7; 
  17. typedef long long ll; 
  18. typedef vector<int> vi; 
  19. typedef vector<vi> vvi; 
  20. typedef pair<int, int> ii; 
  21. typedef vector<ii> vii; 
  22. const int MAXN = int(1e5); 
  23.  
  24.  
  25. int A, n; 
  26. int B[1002][1002];
  27. pair<ii, int> ans[1002][1002];
  28. string dir[1002][1002];  
  29.  
  30. int L(int x) {
  31.   if(x % 10 != 0) return 0; 
  32.   int d = 0; 
  33.   while(x > 0 && x % 10 == 0) 
  34.     x /= 10, d++; 
  35.   return d; 
  36. }
  37. int main() { 
  38. #ifndef ONLINE_JUDGE
  39.   freopen("in.txt", "r", stdin);      
  40.   freopen("out.txt", "w", stdout);
  41. #endif
  42.   int n; scanf("%d", &n); 
  43.   int z = 0, x, y; 
  44.   for(int i = 0; i < n; i++) 
  45.     for(int j = 0; j < n; j++){
  46.       scanf("%d", &A); 
  47.       if(A == 2 || A == 5)
  48.        B[i][j] = A; 
  49.      if(!A)
  50.         { z++, x = i, y = j; continue; }
  51.      if(A && A % 10 == 0) {
  52.       B[i][j] = 1; 
  53.       while(A % 10 == 0) A/= 10, B[i][j] *= 10;
  54.      }
  55.     }
  56.   if(z) {
  57.     string res = ""; 
  58.     for(int i = 0; i < y; i++) res += "R"; 
  59.     for(int i = 0; i < n - 1; i++) res += "D"; 
  60.     for(int i = y+1; i < n; i++) res += "R"; 
  61.     puts("0"); 
  62.     puts(res.c_str()); 
  63.     return 0; 
  64.   }
  65.   dir[0][0] = ""; 
  66.   ans[0][0] = mp(ii(B[0][0]==2, B[0][0]== 5), L(B[0][0])); 
  67.   for(int i = 1; i < n; i++) {
  68.     ans[i][0].fr.fr = (B[i][0] == 2) + ans[i - 1][0].fr.fr;
  69.     ans[i][0].fr.sc = (B[i][0] == 5) + ans[i - 1][0].fr.sc;
  70.     ans[i][0].sc    = L(B[i][0]) + ans[i - 1][0].sc;
  71.     dir[i][0] = dir[i - 1][0] + "D"; 
  72.  
  73.     ans[0][i].fr.fr = (B[0][i] == 2) + ans[0][i - 1].fr.fr;
  74.     ans[0][i].fr.sc = (B[0][i] == 5)+ ans[0][i - 1].fr.sc;
  75.     ans[0][i].sc    = L(B[0][i]) + ans[0][i - 1].sc;
  76.     dir[0][i] = dir[0][i - 1] + "R"; 
  77.   }
  78.   for(int i = 1; i < n; i++) {
  79.     for(int j = 1; j < n; j++) {
  80.       if(ans[i][j - 1].sc + min(ans[i][j - 1].fr.fr, ans[i][j - 1].fr.sc) <= 
  81.         ans[i - 1][j].sc + min(ans[i - 1][j].fr.fr, ans[i - 1][j].fr.sc)) {
  82.         dir[i][j] = dir[i][j - 1] + "R"; 
  83.         ans[i][j].fr.fr = (B[i][j] == 2) + ans[i][j - 1].fr.fr; 
  84.         ans[i][j].fr.sc = (B[i][j] == 5) + ans[i][j - 1].fr.sc; 
  85.         ans[i][j].sc    = L(B[i][j]) + ans[i][j - 1].sc; 
  86.       }else {
  87.         dir[i][j] = dir[i - 1][j] + "D"; 
  88.         ans[i][j].fr.fr = (B[i][j] == 2) + ans[i - 1][j].fr.fr; 
  89.         ans[i][j].fr.sc = (B[i][j] == 5) + ans[i - 1][j].fr.sc; 
  90.         ans[i][j].sc    = L(B[i][j]) + ans[i - 1][j].sc; 
  91.       }
  92.     }
  93.   }
  94.   /*for(int i = 0; i < n; i++) {
  95.     for(int j = 0; j < n; j++) {
  96.       cout << ans[i][j].fr.fr << " " << ans[i][j].fr.sc << "\n"; 
  97.     }
  98.     cout << "\n";
  99.   }*/
  100.   cout << min(ans[n-1][n-1].fr.fr, ans[n-1][n-1].fr.sc) + ans[n-1][n-1].sc << "\n" << dir[n-1][n-1] << "\n"; 
  101. }
  102.  
Success #stdin #stdout 0.01s 22888KB
comments (?)
stdin 
2
2 2
0 5
3
2 2 5
2 2 5
2 2 5
stdout 
0
DR
https://ideone.com/1Juljl
language:
C++14 (gcc 8.3)
created:
9 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!