1. /*
2.   Method 2 for chef and land problem
3.   Starting from capital and tracing down all non-prohibited regions
4.   Then reverse string and exchange L and R, and U and D
5. */
6. #include<bits/stdc++.h>
7. using namespace std;
8. string str,dir;
9. double dist;
10. int l,x_c,y_c,n,m,counter;
11. char arr[21][21];
12. inline void move_as_str(int &i,int &j,char c){
13. int i_tmp = i;
14. int j_tmp = j;
15. switch(c){
16. case 'L' : --j_tmp;
17. break;
18. case 'R' : ++j_tmp;
19. break;
20. case 'U' : --i_tmp;
21. break;
22. case 'D' : ++i_tmp;
23. break;
24. }
25. if(i_tmp<n && j_tmp<m){
26. if(arr[i_tmp][j_tmp]!='*'){
27. i = i_tmp;
28. j = j_tmp;
29. }
30. }
31. }
32. void optimal_motion(int x,int y){
33. int i,j,k;
34. arr[x][y] = '*';
35. for(k=0;k<4;++k){
36. i=x;
37. j=y;
38. move_as_str(i,j,dir[k]);
39. if(arr[i][j]=='.' && (i!=x||j!=y)){
40. str += dir[k];
41. optimal_motion(i,j);
42. }
43. }
44. }
46. char c;
47. reverse(str.begin(),str.end());
48. l = str.length();
49. for(int i=0;i<l;++i){
50. c = str[i];
51. switch(c){
52. case 'L':c='R';
53. break;
54. case 'R':c='L';
55. break;
56. case 'U':c='D';
57. break;
58. case 'D':c='U';
59. break;
60. }
61. str.replace(i,1,1,c);
62. }
63.
64. }
65. int main(){
66. int i,j;
67. counter = 0;
68. str = "";
69. dir = "LRDU";
70. scanf("%d%d",&n,&m);
71. for(i=0;i<n;++i){
72. cin.ignore();
73. for(j=0;j<m;++j){
74. scanf("%c",*(arr+i)+j);
75. if(arr[i][j]=='C'){
76. x_c = i;
77. y_c = j;
78. }
79. if(arr[i][j]=='.')
80. ++counter;
81. }
82. }
83. optimal_motion(x_c,y_c);
85. cout<<str<<endl;
86. }
87.
Success #stdin #stdout 0s 2868KB
stdin
5 7
*******
*.....*
*.***.*
*.*C..*
*******
stdout
UURRRRDDLL