Advertisement
Guest User

Untitled

a guest
Sep 24th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.20 KB | None | 0 0
  1.  
  2. /*   In The Name of Allah   */
  3.  
  4. #include <algorithm>
  5. #include <bitset>
  6. #include <cassert>
  7. #include <cctype>
  8. #include <climits>
  9. #include <cmath>
  10. #include <complex>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <ctime>
  15. #include <deque>
  16. #include <fstream>
  17. #include <functional>
  18. #include <iomanip>
  19. #include <iostream>
  20. #include <limits>
  21. #include <list>
  22. #include <map>
  23. #include <numeric>
  24. #include <queue>
  25. #include <set>
  26. #include <sstream>
  27. #include <stack>
  28. #include <string>
  29. #include <utility>
  30. #include <vector>
  31.  
  32. using namespace std;
  33.  
  34. /* Math */
  35. template < class T > inline T GCD(T a , T b){ if(a < 0) return GCD(-a , b) ; if(b < 0) return GCD(a , -b) ; return (b == 0) ? a : GCD(b , a % b) ; }
  36. template < class T > inline T LCM(T a , T b){ if(a < 0) return LCM(-a , b) ; if(b < 0) return LCM(a , -b) ; return a * (b / GCD(a , b)) ; }
  37. template < class T > inline bool isPrime(T n){ if(n < 2) return false ; for(T i = 2 ; i * i <= n ; i++) if(n % i == 0) return false ; return true ; }
  38. template < class T > vector <T> Divisor(T num){ vector <T> res ; res.clear() ; for(int i = 1 ; i <= num/2 ; i++) if(num % i == 0) res.push_back(i) ; return res ; }
  39. template < class T , class M > inline T POWER(T x , M y){/* (x ^ y) compute to 2^63 */ T temp = 1 ; if(y == 0) return 1 ; for(int i = 1 ; i <= y ; i++) temp *= x  ; return temp ;}
  40.  
  41. /* Manipulation */
  42. template < class T , class M > bool Exist(T x , M element) { for(int i = 0 ; i < x.size() ; i++) if(x[i] == element) return true ; return false ; }
  43. template < class T > vector <T> Unique(vector <T> v){ T temp ; vector <T> res ; res.clear() ; for(int i = 0 ; i  < v.size() ; i++){temp = v[i] ; if(Exist(res,temp) == false) res.push_back(temp) ; } return res ; }
  44. template < class T > vector <T> Parse(T temp){ vector <T> ans ; ans.clear() ; T s ; istringstream is(temp) ; while(is >> s){ ans.push_back(s) ; } return ans ; }
  45. template < class T > string toString(T x) {stringstream s ; s << x; return s.str() ; }
  46. template < class T > long long toInt(T x) {istringstream is(x) ; long long num  ; is >> num ; return num ; }
  47.  
  48. template< class T > inline void checkMin(T &a , T b){ if(b < a) a = b ; }
  49. template< class T > inline void checkMax(T &a , T b){ if(b > a) a = b ; }
  50.  
  51. bool isLowerCase(char c){ return (c >= 'a' &&  c <= 'z') ; }
  52. bool isUpperCase(char c){ return (c >= 'A' &&  c <= 'Z') ; }
  53. char toLowerCase(char c){ return (isUpperCase(c) ? (c + 32) : c) ; }
  54. char toUpperCase(char c){ return (isLowerCase(c) ? (c - 32) : c) ; }
  55. bool isLetter ( char c ){ return (isUpperCase(c)) || (isLowerCase(c)) ; }
  56. bool isDigit  ( char c ){ return (c >= '0' &&  c <= '9') ; }
  57.  
  58. /* Debug */
  59. template < class T > void print(T ans){ for(unsigned int i = 0 ; i < ans.size() ; i++ ) cout << ans[i] << " " ;  cout << endl ; }
  60. template < class T > void print2(T ans){ cout << ans ;  cout << endl ; }
  61.  
  62. typedef long long LL ;
  63. #define ALL(a)              (a).begin(),(a).end()
  64. #define SZ(v)               ((int)(v).size())
  65. #define Clear(x)            memset(x , 0 , sizeof(x))
  66. #define FOR(i,start,end)    for(int i = start ; i < end ; i++)
  67. #define REP(i,start,end)    for(int i = start ; i >= end ; i--)
  68. #define FOREACH(it,x)       for(it = (x.begin()) ; it != (x).end() ; it ++)
  69.  
  70. #define MAX_N 64 + 10
  71. //bool M[MAX_N][MAX_N] ;// adjacency matrix (can have at most MAX_N vertices)
  72. int color[MAX_N] ;// 0 is white, 1 is gray and 2 is black
  73. int dist[MAX_N] ;// dist[v] is the distance from source to v
  74. int parent[MAX_N] ;// parent[v] is the parent of v in the shortest path from source to v
  75.  
  76.  
  77. // knight moves
  78. int dx[] = {-2 , -1 , +1 , +2 , +2 , +1 , -1 , -2} ;
  79. int dy[] = {+1 , +2 , +2 , +1 , -1 , -2 , -2 , -1} ;
  80.  
  81. int number(string s){
  82.     return ((s[0] - 'a') + 1 ) + (((s[1] - '0') - 1) * 8 ) ;
  83.         /*
  84.             chessBoard :
  85.              . . . . . . . .
  86.             8               .
  87.             7               .
  88.             6               .
  89.             5               .
  90.             4               .
  91.             3               .
  92.             2               .
  93.             1               .
  94.              a b c d e f g h
  95.         */
  96.         // (s[1] - 1) * 8 + (s[0] - 'a')
  97.         // for example : b2
  98.         // New = ('b' - 'a' + 1) + ((2 - 1) * 8)
  99.         // New = 2 + 8 = 10
  100. }
  101. int main()// 439 - Knight Moves
  102. {
  103.     //freopen ("input.in","r",stdin) ;
  104.     ifstream cin("input.in") ;
  105.  
  106.  
  107.     string source , end ;
  108.     while(cin >> source >> end){
  109.         queue < string > q ;// The BFS queue to represent the visited set
  110.         int ans = -1 ;
  111.  
  112.         memset(color , 0 , sizeof(color)) ;// set all vertices to be "unvisited"
  113.         memset(dist , 0xFF77 , sizeof(dist)) ;// distance is Infinity initially, meaning "cannot be reached"
  114.         memset(parent , -1 , sizeof(parent)) ;// 1 is not a vertex, meaning "no parent so far"
  115.  
  116.         // Initializing properties of the source vertex
  117.         color[number(source)] = 1 ;
  118.         dist[number(source)] = 0 ;
  119.         parent[number(source)] = -1 ;
  120.         q.push(source) ;
  121.         while(!q.empty()){
  122.             string u = q.front() ;// get first untouched vertex
  123.             q.pop() ;
  124.             /*
  125.             if(u == end){// find goal
  126.                 ans = dist[number(u)] ;
  127.                 break ;
  128.             }
  129.             */
  130.             FOR(i , 0 , 8){
  131.                 string v ;
  132.                 if(u[0] + dy[i] >= 'a' && u[0] + dy[i] <= 'h'){// col : 'a' <= s[0] + dx[i] <= 'h'
  133.                     if((u[1] - '0') + dx[i] >= 1 && (u[1] - '0') + dx[i] <= 8){// row : 1 <= s[1] + dx[i] <= 8
  134.                         v  = (u[0] + dx[i]) ;
  135.                         v += (u[1] + dy[i]) ;
  136.                         if(color[number(v)] == 0){
  137.                             color[number(v)] = 1 ;
  138.                             dist[number(v)] = dist[number(u)] + 1 ;
  139.                             parent[number(v)] = number(u) ;
  140.                             q.push(v) ;
  141.                             if(v == end){
  142.                                 ans = dist[number(v)] ;
  143.                                 goto SKIP ;
  144.                             }
  145.                         }
  146.                     }
  147.                 }
  148.             }// end of for(i)  
  149.             color[number(u)] = 2 ;
  150.         }// end of BFS
  151.         SKIP : cout << ans << endl ;
  152.     }// end of (I/O)
  153.  
  154.  
  155. return 0 ;
  156. }
  157. /*
  158. ---------------------------------------------
  159. Input:
  160. ---------
  161. e2 e4
  162. a1 b2
  163. b2 c3
  164. a1 h8
  165. a1 h7
  166. h8 a1
  167. b1 c3
  168. f6 f6
  169.  
  170. ---------------------------------------------
  171. Output:
  172. ---------
  173. To get from e2 to e4 takes 2 knight moves.
  174. To get from a1 to b2 takes 4 knight moves.
  175. To get from b2 to c3 takes 2 knight moves.
  176. To get from a1 to h8 takes 6 knight moves.
  177. To get from a1 to h7 takes 5 knight moves.
  178. To get from h8 to a1 takes 6 knight moves.
  179. To get from b1 to c3 takes 1 knight moves.
  180. To get from f6 to f6 takes 0 knight moves.
  181.  
  182. ---------------------------------------------
  183. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement