fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <map>
  5. #include <cstring>
  6. #define pb push_back
  7. using namespace std;
  8.  
  9. typedef vector<int> vi;
  10. typedef pair<int, int> pii;
  11.  
  12. const int N = 123;
  13. const int INF = 1000000000;
  14.  
  15. map<int, vector<pii> > pos;
  16. int dp[N][N];
  17.  
  18. int manhattan_dist(pii p1, pii p2) {
  19. 	return abs(p1.first - p2.first) + abs(p1.second - p2.second);
  20. }
  21.  
  22. int optimize(int n, int k) {
  23. 	int global_min = INF;
  24. 	for(auto p: pos[k]) {
  25. 		dp[p.first][p.second] = 0;
  26. 	}
  27.  
  28. 	for(int i = k - 1; i >= 1 ; i--) {
  29. 		for(auto p1: pos[i]) {
  30. 			int min_cost = INF;
  31. 			for(auto p2: pos[i + 1]) {
  32. 				int cur_cost = manhattan_dist(p1, p2) + dp[p2.first][p2.second];
  33. 				if (cur_cost < min_cost) {
  34. 					min_cost = cur_cost;
  35. 				}
  36. 			}
  37. 			dp[p1.first][p1.second] = min_cost;
  38. 			if (i == 1) {
  39. 				global_min = min(global_min, min_cost);
  40. 			}
  41. 		}
  42. 	}
  43. 	return global_min;
  44. }
  45.  
  46. void solve() {
  47. 	memset(dp, INF, sizeof(dp));
  48. 	pos.clear();
  49. 	int n, k; cin >> n >> k;
  50. 	if(k == 1) {
  51. 	    cout << "0\n";
  52. 	    return;
  53. 	}
  54. 	int x;
  55. 	for(int i = 1 ; i <= n ; i++) {
  56. 		for(int j = 1 ; j <= n ; j++) {
  57. 			cin >> x;
  58. 			if(pos.find(x) == pos.end()) {
  59. 				pos[x] = vector<pii>();
  60. 			}
  61. 			pos[x].pb({i, j});
  62. 		}
  63. 	}
  64. 	int ans;
  65. 	ans = optimize(n, k);
  66. 	cout << ans << "\n";
  67. }
  68.  
  69. int main() {
  70. 	int t; cin >> t;
  71. 	while(t--) solve();
  72. }
Time limit exceeded #stdin #stdout 5s 3314284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hmkN01
language:
C++14 (gcc 8.3)
created:
4 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!