fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3.  
  4.  
  5. using namespace std;
  6.  
  7. // fnc2 追加 前のは無駄が多すぎた  9/3 17:20 
  8. // 依然として低い高さ制限(10)に甘えている
  9. int fnc2(const string s){
  10. 	int n=s.size();
  11. 	vector<int> va, vb(1,0);
  12. 	for(int i=0; i< n-1; i++){
  13. 		if(s[i]<s[i+1]){
  14. 			for(int j=s[i];j<s[i+1];j++) va.push_back(j-'0');
  15. 		}else if(s[i]>s[i+1]){
  16. 			for(int j=s[i];j>s[i+1];j--) va.push_back(j-'0');
  17. 		}
  18. 	}
  19. 	for(;;){
  20. 		int cr=va.back();
  21. 		vb.push_back(cr);
  22. 		if(cr==10) break;
  23. 		va.pop_back();
  24. 	}
  25. 	//もろ2次元BFS でよかった?
  26. 	const int dy[]={1,1,-1,-1}, dx[]={1,-1,1,-1};  //X形で4方向
  27. 	const int gy = va.size(), gx = vb.size();
  28. 	vector<vector<int> > d(gy, vector<int>(gx, 9999999));
  29. 	queue< pair<int,int> > que;
  30. 	que.push(make_pair(0,0)); d[0][0]=0;
  31. 	while(!que.empty()){
  32. 		int cy,cx; tie(cy,cx) = que.front();
  33. 		que.pop();
  34. 		for(int i=0; i<4; i++){
  35. 			int ny=cy+dy[i], nx=cx+dx[i];
  36. 			if(ny<0 || ny>=gy || nx<0 || nx>=gx) continue;
  37. 			if(va[ny] != vb[nx]) continue;
  38. 			if(d[ny][nx] > d[cy][cx] + 1){
  39. 				que.push( make_pair(ny, nx) );
  40. 				d[ny][nx] = d[cy][cx] + 1;
  41. 				if(ny==gy-1 && nx==gx-1){
  42. 					return d[ny][nx];
  43. 				}
  44. 			}
  45. 		}
  46. 	}
  47. 	return -1;
  48. }
  49.  
  50. int fnc(const string s){
  51. 	int n=s.size();
  52. 	vector<int> va, vb={0};
  53. 	for(int i=0; i< n-1; i++){
  54. 		if(s[i]<s[i+1]){
  55. 			for(int j=s[i];j<s[i+1];j++) va.push_back(j-'0');
  56. 		}else if(s[i]>s[i+1]){
  57. 			for(int j=s[i];j>=s[i+1]+1;j--) va.push_back(j-'0');
  58. 		}
  59. 	}
  60. 	while(1){
  61. 		int cr=va.back();
  62. 		vb.push_back(cr);
  63. 		if(cr==10) break;
  64. 		va.pop_back();
  65. 	}
  66. 	const int na=va.size(),  nb=vb.size(), INF = 1<<28;
  67. 	vector<vector<int>> cp(na+2, vector<int>(nb+2, INF));
  68. 	cp[0][0] =0;
  69. 	for(int _g ; _g<1e6; _g++){
  70. 		vector<vector<int>> np(na+2, vector<int>(nb+2, INF));
  71. 		for(int j=0;j<na;j++) for(int k=0;k<nb;k++) if(cp[j][k] < INF){
  72. 			int c1=cp[j][k] + 1;
  73. 			//np[j][k] = min( cp[j][k], np[j][k]);
  74. 			//進める方向に進んでみよう
  75. 			if(j+1<na && k+1<nb && va[j+1] == vb[k+1])
  76. 				np[j+1][k+1] = min(np[j+1][k+1], c1);
  77. 			if(k>0 && j+1<na && va[j+1] == vb[k-1])
  78. 				np[j+1][k-1] = min(np[j+1][k-1],c1);
  79. 			if(k>0 && j>0 &&  va[j-1]==vb[k-1])
  80. 				np[j-1][k-1] = min( np[j-1][k-1],c1);
  81. 			if(j>0 && k+1<nb && va[j-1] == vb[k+1])
  82. 				np[j-1][k+1] = min(np[j-1][k+1], c1);
  83. 		}
  84. 		swap(cp, np);
  85. 		if(cp[na-1][nb-1] < INF) break; //最初が最小値だと思う
  86. 	}
  87. 	return cp[na-1][nb-1];
  88. }
  89. int main()
  90. {
  91. 	string s; 
  92.  
  93. 	while(cin >>s){
  94. 		//cout << s << " ---> " << fnc(s) <<endl;
  95. 		cout << s << "  --> " << fnc2(s) <<endl;
  96. 	}
  97. 	return 0;
  98. }
  99. /*
  100. "073:0" -> 18
  101. "07362:450" -> 36
  102. "06464:36470" -> 42
  103. "0827171:28480" -> 66
  104. "0737491:28180" -> 146
  105. "05374734372747484:184618186912120" -> ?
  106. */
  107.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
073:0                            
07362:450                        
06464:36470                      
0827171:28480                    
0737491:28180                    
05374734372747484:184618186912120
stdout
copy 
073:0  --> 18
07362:450  --> 36
06464:36470  --> 42
0827171:28480  --> 66
0737491:28180  --> 146
05374734372747484:184618186912120  --> 400
https://ideone.com/2sIaGw
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!