fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define _nhatminh  int main()
  3. #define ll long long
  4. #define str string
  5. #define fir first
  6. #define sec second
  7. #define ld long double
  8. #define pb push_back
  9. #define MOD 100000009
  10. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define piint pair < int , int >
  13. #define piL pair < int , ll>
  14. #define pLL pair < ll , ll >
  15. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  16. using namespace std;
  17. const int Max_n=2000;
  18. char a[Max_n+3][Max_n+3];
  19. str dp[Max_n+3][Max_n+3] ;
  20. int n , m ; 
  21. int dx[] = { 0 , 1 , 1 , -1 };
  22. int dy[] = { 1 , 0 , 0 , 0 } ;
  23. int trace[Max_n+3][Max_n+3] ; 
  24. void bfs ( int i , int j ){
  25. 	dp[1][1] = a[1][1] ;
  26. 	queue < piint > q ;
  27. 	q.push( { 1 , 1 }) ;
  28. 	while ( q.size()){
  29. 		piint v = q.front() ;
  30. 		q.pop() ;
  31. 		for (int i = 0 ; i < 2 ; i ++ ){
  32. 			int x = v.fir + dx[i] ;
  33. 			int y = v.sec + dy[i] ;
  34. 			if ( x >= 1 && x <= n 
  35. 				&& y >= 1 && y <= m ){
  36. 				str new_dp = dp[v.fir][v.sec] + a[x][y] ;
  37. 				if (dp[x][y].empty()){
  38. 					dp[x][y] = new_dp ;
  39. 					q.push({x,y}) ;
  40. 					continue ;
  41. 				}
  42. 				if ( dp[x][y] <= new_dp ) continue ;
  43. 				dp[x][y] = new_dp ;
  44. 				q.push({x,y});
  45. 			}
  46. 		}
  47. 	}
  48. }
  49. int kt[Max_n+3][Max_n+3] ;   
  50. void bfs01 ( int i , int j ){
  51. 	queue < piint > d ;
  52. 	d.push({i,j}) ;
  53. 	while ( d.size()) {
  54. 		piint v = d.front() ;
  55. 		//d.pop_front() ;
  56. 		d.pop();
  57. 		char i_1 = 0, i_2 = 0;
  58. 		for (int i = 0 ; i < 2 ; i ++ ){
  59. 			int x = v.fir + dx[i] ;
  60. 			int y = v.sec + dy[i] ;
  61. 			if ( x >= 1 && x <= n 
  62. 				&& y >= 1 && y <= m ){
  63. 				if ( i == 0 ) i_1 = a[x][y] ;
  64. 				else i_2 = a[x][y] ;
  65. 			}
  66. 		}
  67. 		int x = v.fir + dx[0], y = v.sec + dy[0]; 
  68. 		int x1 = v.fir + dx[1] , y1 = v.sec + dy[1] ;
  69. 		if ( i_1 != 0 || i_2 != 0){
  70. 		int cp = min ( i_1 , i_2 );
  71. 			if (cp== 0){
  72. 				cp = max ( i_1 , i_2) ;
  73. 			}
  74. 			if ( i_1 == i_2){
  75. 				if (kt[x][y] > cp){
  76. 					kt[x][y] = cp ;
  77. 					trace[x][y] = 0 ;
  78. 					d.push({x,y}) ;
  79. 				}
  80. 				if (kt[x1][y1] > cp){
  81. 					kt[x1][y1] = cp ;
  82. 					trace[x1][y1] = 1 ;
  83. 					d.push({x1,y1}) ;
  84. 				}
  85.  
  86. 				//cout << v.fir << ' ' << v.sec << ' ' << x << ' ' << y << ' ' << x1 << ' ' << y1 << '\n';
  87. 			}
  88. 			else if ( i_1 > i_2 ){
  89. 				if (kt[x][y] > cp){
  90. 					kt[x][y] = cp ;
  91. 					trace[x][y] = 0 ;
  92. 					d.push({x,y}) ;
  93. 				}
  94. 			}
  95. 			else {
  96. 				if (kt[x1][y1] > cp){
  97. 					kt[x1][y1] = cp ;
  98. 					trace[x1][y1] = 1 ;
  99. 					d.push({x1,y1}) ;
  100. 				}
  101. 			}
  102. 		}
  103.  	}
  104. }
  105. void TRY_VET (){
  106. 	piint ou ;
  107. 	ou.fir = n , ou.sec = m ;
  108. 	std::vector<char> ans;
  109. 	while ( n != 1|| m != 1){
  110. 		int i = trace[n][m] ;
  111. 		//cout << i << '\n';
  112. 		ans.pb(a[n][m]) ;
  113. 		n -= dx[i];
  114. 		m -= dy[i] ;
  115. 	}
  116. 	ans.pb(a[1][1]);
  117. 	reverse(ALL(ans));
  118. 	for (auto x : ans) {
  119. 		cout << x ;
  120. 	}
  121. }
  122. void sub_FULL(){
  123. 	for (int i = 1 ; i <= n; i ++ )
  124. 		for (int j = 1 ; j <= m ; j ++ )
  125. 			kt[i][j]= 10000; 
  126. 	bfs01( 1 , 1 ) ;
  127. 	TRY_VET() ;
  128. }
  129. void solve(){
  130. 	cin >> n >> m ;
  131. 	for (int i =1  ; i <= n ; i ++ ){
  132. 		str s ; cin >> s;
  133. 		for (int j =1 ; j <=m ; j ++ ){
  134. 			a[i][j] = s[j-1] ;
  135. 		}
  136. 	}
  137. 	if ( n <= 500 ){
  138. 		bfs(1,1) ;
  139. 		cout << dp[n][m] ;
  140. 		return ;
  141. 	}
  142. 	else sub_FULL() ;
  143. }
  144. _nhatminh{
  145. freopen("spath");
  146. ios_base::sync_with_stdio(0);
  147. cin.tie(0); cout.tie(0);
  148. int q=1;
  149. // cin >> q;
  150. while (q--)
  151. 	solve();
  152. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  153. return (0);
  154. }
Success #stdin #stdout #stderr 0.03s 130780KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed 0.023219s.
https://ideone.com/YJOT1M
language:
C++14 (gcc 8.3)
created:
12 days 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!