fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<stdio.h>
  3. using namespace std;
  4.  
  5. int n, m, dp[1123][1123], choose[1123][1123];
  6. pair<int,int> pos[1123];
  7.  
  8. //좌표 a와 b의 최단 거리
  9. inline int dist(auto &a, auto &b){
  10. 	return abs(a.first - b.first) + abs(a.second - b.second);
  11. }
  12.  
  13. //경찰차의 위치가 각각 pos[x], pos[y]일 때, 현재 상태부터 가능 한 최소 거리의 합
  14. int solve(int x, int y){
  15. 	static int c;
  16. 	//pos[here]을 해결해야 한다.
  17. 	int here = max(x,y)+1;
  18. 	cout<<"x before"<<endl<<"x:"<<x<<"here:"<<here<<" y:"<<y<<"c:"<<c<<" x start"<<endl;
  19. 	if(here == m+2){--c; return 0;}
  20. 	int &ret = dp[x][y];
  21. 	if(ret != -1){--c; return ret;}
  22. 	//x가 이번 사건을 해결한다.
  23. 	++c;
  24. 	int v=solve(here, y);
  25. 	cout<<"solve(here, y): "<<v<<endl;
  26. 	cout<<"x after"<<endl<<"x:"<<x<<"here:"<<here<<" y:"<<y<<"c:"<<c<<" x start"<<endl;
  27. 	ret = v + dist(pos[x], pos[here]);
  28. 	cout<<"ret finish->"<<ret<<" x:"<<x<<" y:"<<y<<" here:"<<here<<"c:"<<c<<endl;
  29. 	//y가 이번 사건을 해결하는게 이득일 경우
  30. 	cout<<"y before"<<endl<<"x:"<<x<<"here:"<<here<<" y:"<<y<<"c:"<<c<<" y start"<<endl;
  31. 	++c;
  32. 	v=solve(x, here);
  33. 	cout<<"solve(x, here): "<<v<<endl;
  34. 	cout<<"y after"<<endl<<"x:"<<x<<"here:"<<here<<" y:"<<y<<"c:"<<c<<" y start"<<endl;
  35. 	int ygo = solve(x, here) + dist(pos[y], pos[here]);
  36. 	cout<<"ygo"<<endl<<ygo<<" y "<<y<<"here "<<here<<endl;
  37. 	if(ygo < ret){
  38. 	ret = ygo;
  39. 		choose[x][y] = 1;
  40. 		cout<<"2"<<endl;
  41. 	}
  42. 	cout<<"ret!"<<ret<<endl;
  43. 	--c;
  44. 	return ret;
  45. }
  46.  
  47. int main(){
  48. 	ios_base::sync_with_stdio(0);
  49. 	cin.tie(0);
  50.  
  51. 	cin >> n >> m;
  52. 	for(int i=2; i<m+2; ++i){cin >> pos[i].first >> pos[i].second;}
  53. 	pos[0] = {1,1};
  54. 	pos[1] = {n,n};
  55. 	memset(dp, -1, sizeof(dp));
  56. 	cout << solve(0, 1) << '\n';
  57.  
  58. 	for(int x = 0, y = 1; max(x,y)+1 < m+2; ){
  59. 		cout << choose[x][y]+1 << '\n';
  60. 		//choose[x][y] = 1일 경우 y가 사건을 해결
  61. 		if(choose[x][y]) y = max(x,y)+1;
  62. 		else x = max(x,y)+1;
  63. 	}
  64. }
  65.  
Success #stdin #stdout 0s 8576KB
comments (?)
stdin
copy 
6
4
1
3
3
2
1
3
4
1
stdout
copy 
x before
x:0here:2 y:1c:0 x start
x before
x:2here:3 y:1c:1 x start
x before
x:3here:4 y:1c:2 x start
x before
x:4here:5 y:1c:3 x start
x before
x:5here:6 y:1c:4 x start
solve(here, y): 0
x after
x:4here:5 y:1c:3 x start
ret finish->5 x:4 y:1 here:5c:3
y before
x:4here:5 y:1c:3 y start
x before
x:4here:6 y:5c:4 x start
solve(x, here): 0
y after
x:4here:5 y:1c:3 y start
x before
x:4here:6 y:5c:3 x start
ygo
7 y 1here 5
ret!5
solve(here, y): 5
x after
x:3here:4 y:1c:1 x start
ret finish->8 x:3 y:1 here:4c:1
y before
x:3here:4 y:1c:1 y start
x before
x:3here:5 y:4c:2 x start
x before
x:5here:6 y:4c:3 x start
solve(here, y): 0
x after
x:3here:5 y:4c:2 x start
ret finish->2 x:3 y:4 here:5c:2
y before
x:3here:5 y:4c:2 y start
x before
x:3here:6 y:5c:3 x start
solve(x, here): 0
y after
x:3here:5 y:4c:2 y start
x before
x:3here:6 y:5c:2 x start
ygo
5 y 4here 5
ret!2
solve(x, here): 2
y after
x:3here:4 y:1c:0 y start
x before
x:3here:5 y:4c:0 x start
ygo
10 y 1here 4
ret!8
solve(here, y): 8
x after
x:2here:3 y:1c:-2 x start
ret finish->11 x:2 y:1 here:3c:-2
y before
x:2here:3 y:1c:-2 y start
x before
x:2here:4 y:3c:-1 x start
x before
x:4here:5 y:3c:0 x start
x before
x:5here:6 y:3c:1 x start
solve(here, y): 0
x after
x:4here:5 y:3c:0 x start
ret finish->5 x:4 y:3 here:5c:0
y before
x:4here:5 y:3c:0 y start
x before
x:4here:6 y:5c:1 x start
solve(x, here): 0
y after
x:4here:5 y:3c:0 y start
x before
x:4here:6 y:5c:0 x start
ygo
2 y 3here 5
2
ret!2
solve(here, y): 2
x after
x:2here:4 y:3c:-2 x start
ret finish->2 x:2 y:3 here:4c:-2
y before
x:2here:4 y:3c:-2 y start
x before
x:2here:5 y:4c:-1 x start
x before
x:5here:6 y:4c:0 x start
solve(here, y): 0
x after
x:2here:5 y:4c:-1 x start
ret finish->5 x:2 y:4 here:5c:-1
y before
x:2here:5 y:4c:-1 y start
x before
x:2here:6 y:5c:0 x start
solve(x, here): 0
y after
x:2here:5 y:4c:-1 y start
x before
x:2here:6 y:5c:-1 x start
ygo
5 y 4here 5
ret!5
solve(x, here): 5
y after
x:2here:4 y:3c:-3 y start
x before
x:2here:5 y:4c:-3 x start
ygo
8 y 3here 4
ret!2
solve(x, here): 2
y after
x:2here:3 y:1c:-5 y start
x before
x:2here:4 y:3c:-5 x start
ygo
9 y 1here 3
2
ret!9
solve(here, y): 9
x after
x:0here:2 y:1c:-7 x start
ret finish->11 x:0 y:1 here:2c:-7
y before
x:0here:2 y:1c:-7 y start
x before
x:0here:3 y:2c:-6 x start
x before
x:3here:4 y:2c:-5 x start
x before
x:4here:5 y:2c:-4 x start
x before
x:5here:6 y:2c:-3 x start
solve(here, y): 0
x after
x:4here:5 y:2c:-4 x start
ret finish->5 x:4 y:2 here:5c:-4
y before
x:4here:5 y:2c:-4 y start
x before
x:4here:6 y:5c:-3 x start
solve(x, here): 0
y after
x:4here:5 y:2c:-4 y start
x before
x:4here:6 y:5c:-4 x start
ygo
5 y 2here 5
ret!5
solve(here, y): 5
x after
x:3here:4 y:2c:-6 x start
ret finish->8 x:3 y:2 here:4c:-6
y before
x:3here:4 y:2c:-6 y start
x before
x:3here:5 y:4c:-5 x start
solve(x, here): 2
y after
x:3here:4 y:2c:-6 y start
x before
x:3here:5 y:4c:-6 x start
ygo
2 y 2here 4
2
ret!2
solve(here, y): 2
x after
x:0here:3 y:2c:-8 x start
ret finish->5 x:0 y:2 here:3c:-8
y before
x:0here:3 y:2c:-8 y start
x before
x:0here:4 y:3c:-7 x start
x before
x:4here:5 y:3c:-6 x start
solve(here, y): 2
x after
x:0here:4 y:3c:-7 x start
ret finish->4 x:0 y:3 here:4c:-7
y before
x:0here:4 y:3c:-7 y start
x before
x:0here:5 y:4c:-6 x start
x before
x:5here:6 y:4c:-5 x start
solve(here, y): 0
x after
x:0here:5 y:4c:-6 x start
ret finish->3 x:0 y:4 here:5c:-6
y before
x:0here:5 y:4c:-6 y start
x before
x:0here:6 y:5c:-5 x start
solve(x, here): 0
y after
x:0here:5 y:4c:-6 y start
x before
x:0here:6 y:5c:-6 x start
ygo
5 y 4here 5
ret!3
solve(x, here): 3
y after
x:0here:4 y:3c:-8 y start
x before
x:0here:5 y:4c:-8 x start
ygo
6 y 3here 4
ret!4
solve(x, here): 4
y after
x:0here:3 y:2c:-10 y start
x before
x:0here:4 y:3c:-10 x start
ygo
7 y 2here 3
ret!5
solve(x, here): 5
y after
x:0here:2 y:1c:-12 y start
x before
x:0here:3 y:2c:-12 x start
ygo
13 y 1here 2
ret!11
11
1
2
1
2
https://ideone.com/Yl34Cg
language:
C++14 (gcc 8.3)
created:
3 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!