Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* In The Name of Allah */
- #include <algorithm>
- #include <bitset>
- #include <cassert>
- #include <cctype>
- #include <climits>
- #include <cmath>
- #include <complex>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <ctime>
- #include <deque>
- #include <fstream>
- #include <functional>
- #include <iomanip>
- #include <iostream>
- #include <limits>
- #include <list>
- #include <map>
- #include <numeric>
- #include <queue>
- #include <set>
- #include <sstream>
- #include <stack>
- #include <string>
- #include <utility>
- #include <vector>
- using namespace std;
- /* Math */
- 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) ; }
- 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)) ; }
- 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 ; }
- 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 ; }
- 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 ;}
- /* Manipulation */
- 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 ; }
- 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 ; }
- 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 ; }
- template < class T > string toString(T x) {stringstream s ; s << x; return s.str() ; }
- template < class T > long long toInt(T x) {istringstream is(x) ; long long num ; is >> num ; return num ; }
- template< class T > inline void checkMin(T &a , T b){ if(b < a) a = b ; }
- template< class T > inline void checkMax(T &a , T b){ if(b > a) a = b ; }
- bool isLowerCase(char c){ return (c >= 'a' && c <= 'z') ; }
- bool isUpperCase(char c){ return (c >= 'A' && c <= 'Z') ; }
- char toLowerCase(char c){ return (isUpperCase(c) ? (c + 32) : c) ; }
- char toUpperCase(char c){ return (isLowerCase(c) ? (c - 32) : c) ; }
- bool isLetter ( char c ){ return (isUpperCase(c)) || (isLowerCase(c)) ; }
- bool isDigit ( char c ){ return (c >= '0' && c <= '9') ; }
- /* Debug */
- template < class T > void print(T ans){ for(unsigned int i = 0 ; i < ans.size() ; i++ ) cout << ans[i] << " " ; cout << endl ; }
- template < class T > void print2(T ans){ cout << ans ; cout << endl ; }
- typedef long long LL ;
- #define ALL(a) (a).begin(),(a).end()
- #define SZ(v) ((int)(v).size())
- #define Clear(x) memset(x , 0 , sizeof(x))
- #define FOR(i,start,end) for(int i = start ; i < end ; i++)
- #define REP(i,start,end) for(int i = start ; i >= end ; i--)
- #define FOREACH(it,x) for(it = (x.begin()) ; it != (x).end() ; it ++)
- #define MAX_N 64 + 10
- //bool M[MAX_N][MAX_N] ;// adjacency matrix (can have at most MAX_N vertices)
- int color[MAX_N] ;// 0 is white, 1 is gray and 2 is black
- int dist[MAX_N] ;// dist[v] is the distance from source to v
- int parent[MAX_N] ;// parent[v] is the parent of v in the shortest path from source to v
- // knight moves
- int dx[] = {-2 , -1 , +1 , +2 , +2 , +1 , -1 , -2} ;
- int dy[] = {+1 , +2 , +2 , +1 , -1 , -2 , -2 , -1} ;
- int number(string s){
- return ((s[0] - 'a') + 1 ) + (((s[1] - '0') - 1) * 8 ) ;
- /*
- chessBoard :
- . . . . . . . .
- 8 .
- 7 .
- 6 .
- 5 .
- 4 .
- 3 .
- 2 .
- 1 .
- a b c d e f g h
- */
- // (s[1] - 1) * 8 + (s[0] - 'a')
- // for example : b2
- // New = ('b' - 'a' + 1) + ((2 - 1) * 8)
- // New = 2 + 8 = 10
- }
- int main()// 439 - Knight Moves
- {
- //freopen ("input.in","r",stdin) ;
- ifstream cin("input.in") ;
- string source , end ;
- while(cin >> source >> end){
- queue < string > q ;// The BFS queue to represent the visited set
- int ans = -1 ;
- memset(color , 0 , sizeof(color)) ;// set all vertices to be "unvisited"
- memset(dist , 0xFF77 , sizeof(dist)) ;// distance is Infinity initially, meaning "cannot be reached"
- memset(parent , -1 , sizeof(parent)) ;// 1 is not a vertex, meaning "no parent so far"
- // Initializing properties of the source vertex
- color[number(source)] = 1 ;
- dist[number(source)] = 0 ;
- parent[number(source)] = -1 ;
- q.push(source) ;
- while(!q.empty()){
- string u = q.front() ;// get first untouched vertex
- q.pop() ;
- /*
- if(u == end){// find goal
- ans = dist[number(u)] ;
- break ;
- }
- */
- FOR(i , 0 , 8){
- string v ;
- if(u[0] + dy[i] >= 'a' && u[0] + dy[i] <= 'h'){// col : 'a' <= s[0] + dx[i] <= 'h'
- if((u[1] - '0') + dx[i] >= 1 && (u[1] - '0') + dx[i] <= 8){// row : 1 <= s[1] + dx[i] <= 8
- v = (u[0] + dx[i]) ;
- v += (u[1] + dy[i]) ;
- if(color[number(v)] == 0){
- color[number(v)] = 1 ;
- dist[number(v)] = dist[number(u)] + 1 ;
- parent[number(v)] = number(u) ;
- q.push(v) ;
- if(v == end){
- ans = dist[number(v)] ;
- goto SKIP ;
- }
- }
- }
- }
- }// end of for(i)
- color[number(u)] = 2 ;
- }// end of BFS
- SKIP : cout << ans << endl ;
- }// end of (I/O)
- return 0 ;
- }
- /*
- ---------------------------------------------
- Input:
- ---------
- e2 e4
- a1 b2
- b2 c3
- a1 h8
- a1 h7
- h8 a1
- b1 c3
- f6 f6
- ---------------------------------------------
- Output:
- ---------
- To get from e2 to e4 takes 2 knight moves.
- To get from a1 to b2 takes 4 knight moves.
- To get from b2 to c3 takes 2 knight moves.
- To get from a1 to h8 takes 6 knight moves.
- To get from a1 to h7 takes 5 knight moves.
- To get from h8 to a1 takes 6 knight moves.
- To get from b1 to c3 takes 1 knight moves.
- To get from f6 to f6 takes 0 knight moves.
- ---------------------------------------------
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement