SHARE
TWEET

Untitled

a guest Oct 11th, 2018 47 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  ID: bradyawn
  3.  PROG: contest
  4.  LANG: C++11
  5.  */
  6.  
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <iomanip>
  10. #include <fstream>
  11. #include <vector>
  12. #include <deque>
  13. #include <string>
  14. #include <cmath>
  15. #include <map>
  16. #include <unordered_map>
  17. #include <utility>
  18. #include <set>
  19. #include <unordered_set>
  20. #include <ctime>
  21. #include <queue>
  22. #include <stack>
  23. #include <bitset>
  24. #include <random>
  25. #include <cstring>
  26. #include <complex>
  27. #include <cassert>
  28.  
  29. using namespace std;
  30.  
  31. typedef long long ll;
  32. typedef long double ld;
  33. typedef pair<int,int> i2;
  34. typedef pair<ll,ll> ll2;
  35.  
  36. int n;
  37.  
  38. int val[11][11];
  39. i2 pos[101];
  40.  
  41. struct S
  42. {
  43.     i2 d; //moves, swaps
  44.     int type;
  45.     int cur;
  46.     int lvl;
  47.     S(int mm, int ss, int tt, int cc, int lv)
  48.     {
  49.         d.first = mm;
  50.         d.second = ss;
  51.         type = tt;
  52.         cur = cc;
  53.         lvl = lv;
  54.     }
  55.     friend bool operator<(const S &lhs, const S &rhs)
  56.     {
  57.         return lhs.d > rhs.d;
  58.     }
  59. };
  60.  
  61. //TP, cur, level
  62. i2 dist[3][101][101];
  63. priority_queue<S> pq;
  64.  
  65. bool f(int x) //x e [1,n]
  66. {
  67.     return (1 <= x && x <= n);
  68. }
  69.  
  70. int main()
  71. {
  72.     //ifstream inf("");
  73.     //ofstream outf("");
  74.     //cout << setprecision(10);
  75.     ios::sync_with_stdio(0); cin.tie(0);
  76.    
  77.     memset(dist, -1, sizeof dist);
  78.    
  79.     cin >> n;
  80.     for (int i = 1; i <= n; i++)
  81.         for (int j = 1; j <= n; j++) {cin >> val[i][j]; pos[val[i][j]] = {i,j}; }
  82.    
  83.     //S(MOVES, SWITCHES, TYPE, CUR, LEVEL)
  84.     // TYPE 0 = KNIGHT
  85.     // TYPE 1 = ROOK
  86.     // TYPE 2 = BISHOP
  87.    
  88.     pq.push(S(0, 0, 0, 1, 1));
  89.     pq.push(S(0, 0, 1, 1, 1));
  90.     pq.push(S(0, 0, 2, 1, 1));
  91.    
  92.     while (!pq.empty())
  93.     {
  94.         auto a = pq.top(); pq.pop();
  95.         int row = pos[a.cur].first;
  96.         int col = pos[a.cur].second;
  97.        
  98.         if (a.cur == a.lvl+1) a.lvl++;
  99.         if (dist[a.type][a.cur][a.lvl].first != -1) continue;
  100.         dist[a.type][a.cur][a.lvl] = a.d;
  101.        
  102.         if (a.lvl == n*n && a.cur == n*n)
  103.         {
  104.             cout << a.d.first << ' ' << a.d.second << '\n';
  105.             return 0;
  106.         }
  107.        
  108.         //repositioning
  109.         if (a.type == 0) // TYPE 0 = KNIGHT
  110.         {
  111.             S b = a; b.d.first++;
  112.            
  113.             if (f(row+2) && f(col+1)) {b.cur = val[row+2][col+1]; pq.push(b);}
  114.             if (f(row+2) && f(col-1)) {b.cur = val[row+2][col-1]; pq.push(b);}
  115.             if (f(row-2) && f(col+1)) {b.cur = val[row-2][col+1]; pq.push(b);}
  116.             if (f(row-2) && f(col-1)) {b.cur = val[row-2][col-1]; pq.push(b);}
  117.            
  118.             if (f(row+1) && f(col+2)) {b.cur = val[row+1][col+2]; pq.push(b);}
  119.             if (f(row+1) && f(col-2)) {b.cur = val[row+1][col-2]; pq.push(b);}
  120.             if (f(row-1) && f(col+2)) {b.cur = val[row-1][col+2]; pq.push(b);}
  121.             if (f(row-1) && f(col-2)) {b.cur = val[row-1][col-2]; pq.push(b);}
  122.         }
  123.         else if (a.type == 1) // TYPE 1 = ROOK
  124.         {
  125.             S b = a; b.d.first++;
  126.             for (int i = 1; i <= n; i++) if (i != row) { b.cur = val[i][col]; pq.push(b); }
  127.             for (int i = 1; i <= n; i++) if (i != col) { b.cur = val[row][i]; pq.push(b); }
  128.         }
  129.         else // TYPE 2 = BISHOP
  130.         {
  131.             S b = a; b.d.first++;
  132.             for (int i = 1; i <= n; i++)
  133.             {
  134.                 if (f(row+i) && f(col+i)) { b.cur = val[row+i][col+i]; pq.push(b); }
  135.                 if (f(row+i) && f(col-i)) { b.cur = val[row+i][col-i]; pq.push(b); }
  136.                 if (f(row-i) && f(col+i)) { b.cur = val[row-i][col+i]; pq.push(b); }
  137.                 if (f(row-i) && f(col-i)) { b.cur = val[row-i][col-i]; pq.push(b); }
  138.             }
  139.         }
  140.        
  141.         //swapping out pieces, switch++
  142.         a.d.first++;
  143.         a.d.second++;
  144.         a.type++; a.type %= 3;
  145.         pq.push(a);
  146.         a.type++; a.type %= 3;
  147.         pq.push(a);
  148.     }
  149.    
  150.     return 0;
  151.    
  152. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top