Created
October 21, 2019 23:30
-
-
Save BWbwchen/85e142fe77b06e5f1e38e2b104d507b0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#define DEBUG | |
#define MAXN 1e9 | |
#include <bits/stdc++.h> | |
#define MAXIMUM 10000 | |
using namespace std; | |
template<class T> | |
class _queue | |
{ | |
private: | |
T* q; | |
int begin, end; | |
int total; | |
public: | |
_queue(){ | |
q = new T[MAXIMUM]; | |
begin = -1; | |
end = -1; | |
total = 0; | |
} | |
~_queue() { | |
delete [] q; | |
} | |
inline bool empty() {return (total == 0)?true:false;}; | |
inline int size() {return total;}; | |
T front() { | |
if (empty()) throw "empty!!!"; | |
return q[begin]; | |
} | |
T back() { | |
if (empty()) throw "empty!!!"; | |
return q[end]; | |
} | |
void push(const T& item); | |
void pop(); | |
}; | |
vector<int > solve (pair<int , int > , pair<int , int > ); | |
bool valid (pair<int , int > ); | |
vector<pair<int , int > > visited; | |
class Data { | |
public : | |
int row; | |
int col; | |
int cost; | |
Data(pair<int , int > a,int count = 0) { | |
row = a.first; | |
col = a.second; | |
cost = count; | |
} | |
Data() { | |
row = 0; | |
col = 0; | |
cost = 0; | |
} | |
}; | |
int main() | |
{ | |
ios_base::sync_with_stdio(0); cin.tie(0); | |
#ifdef DEBUG | |
freopen("in.in", "r", stdin); | |
#endif | |
string a1; | |
string a2; | |
vector<int > path ; | |
int count = 0; | |
while (cin >> a1 >> a2) { | |
pair<int, int > a (a1[0]-'a', a1[1]-'1'); | |
pair<int, int > b (a2[0]-'a', a2[1]-'1'); | |
path = solve(a, b); | |
int smallest = MAXN; | |
for (vector<int >::iterator it = path.begin(); it != path.end(); it++) { | |
if (*it < smallest) smallest = *it; | |
//cout << *it << " "; | |
} | |
path.clear(); | |
visited.clear(); | |
cout << "number " << ++count << "'s case: "; | |
cout << smallest << endl; | |
} | |
return 0; | |
} | |
bool valid (pair<int , int > test) | |
{ | |
if (0 > test.first || test.first > 7 || 0 > test.second || test.second > 7) { | |
return false; | |
} | |
if (find(visited.begin(), visited.end(), test) == visited.end()) { | |
// can't find | |
return true; | |
} | |
return false; | |
} | |
vector<int > solve (pair<int , int > begin, pair<int , int > end ) | |
{ | |
_queue<Data > to_judge; | |
pair<int , int > temp; | |
vector<int > record; | |
to_judge.push(Data(begin)); | |
// int count = 0; | |
while(!to_judge.empty()) { | |
//cout << count++ << endl; | |
auto to_extend = to_judge.front(); | |
to_judge.pop(); | |
pair<int , int > t = {to_extend.row, to_extend.col}; | |
if ( t == end) { | |
record.push_back(to_extend.cost); | |
continue; | |
} | |
visited.push_back({to_extend.row, to_extend.col}); | |
// extend | |
temp = {to_extend.row+2, to_extend.col+3}; | |
if (valid(temp)) to_judge.push(Data(temp, to_extend.cost+1)); | |
temp = {to_extend.row-2, to_extend.col+3}; | |
if (valid(temp)) to_judge.push(Data(temp, to_extend.cost+1)); | |
temp = {to_extend.row+2, to_extend.col-3}; | |
if (valid(temp)) to_judge.push(Data(temp, to_extend.cost+1)); | |
temp = {to_extend.row-2, to_extend.col-3}; | |
if (valid(temp)) to_judge.push(Data(temp, to_extend.cost+1)); | |
temp = {to_extend.row+3, to_extend.col+2}; | |
if (valid(temp)) to_judge.push(Data(temp, to_extend.cost+1)); | |
temp = {to_extend.row-3, to_extend.col+2}; | |
if (valid(temp)) to_judge.push(Data(temp, to_extend.cost+1)); | |
temp = {to_extend.row+3, to_extend.col-2}; | |
if (valid(temp)) to_judge.push(Data(temp, to_extend.cost+1)); | |
temp = {to_extend.row-3, to_extend.col-2}; | |
if (valid(temp)) to_judge.push(Data(temp, to_extend.cost+1)); | |
} | |
return record; | |
} | |
template<class T> | |
void _queue<T>::push (const T& item) | |
{ | |
if (begin == -1) { | |
begin = 0; | |
} | |
end = (end+1)%MAXIMUM; | |
q[end]= item; | |
total++; | |
} | |
template<class T> | |
void _queue<T>::pop () | |
{ | |
if (begin == -1 || begin > end) return ; | |
// begin > end : think about just one node and want to pop it | |
begin = (begin+1)%MAXIMUM; | |
total--; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment