#include #include #include #include #include #include using namespace std; enum Color { white, gray, black }; struct Vertex { int id; Color color; int dist; int pred; Vertex(int n) { id = n; color =white; pred = -1; if (id==0) { dist = 0; color = gray; pred = 0; } else { dist = INT_MAX; } } }; struct Board { int _n; int _a; int _b; vector _nodes; Board(int n, int a, int b) { _n = n; _a = a; _b = b; for (int i=0; i& nbrs) { int row = v / _n; int col = v % _n; int x = row + _a; int y = col + _b; if (x<_n && x>=0 && y>=0 && y <_n) nbrs.push_back(x*_n+y); y = col - _b; if (x<_n && x>=0 && y>=0 && y <_n) nbrs.push_back(x*_n+y); x = row + _b; y = col + _a; if (x<_n && x>=0 && y>=0 && y <_n) nbrs.push_back(x*_n+y); y = col - _a; if (x<_n && x>=0 && y>=0 && y <_n) nbrs.push_back(x*_n+y); x = row - _a; y = col - _b; if (x<_n && x>=0 && y>=0 && y <_n) nbrs.push_back(x*_n+y); y = col + _b; if (x<_n && x>=0 && y>=0 && y <_n) nbrs.push_back(x*_n+y); x = row - _b; y = col - _a; if (x<_n && x>=0 && y>=0 && y <_n) nbrs.push_back(x*_n+y); y = col + _a; if (x<_n && x>=0 && y>=0 && y <_n) nbrs.push_back(x*_n+y); } /* BFS algorithm */ int ShortestDist() { queue q; q.push(_nodes[0]); while (q.empty() == false) { Vertex * u = q.front(); q.pop(); vector nbrs; getNeighbors(u->id, nbrs); // copy(nbrs.begin(), nbrs.end(), ostream_iterator(cout, " ")); // cout << endl; for (int i=0; icolor == white) { v->color = gray; v->dist = u->dist + 1; v->pred = u->id; q.push(v); } } u->color = black; } Vertex * last = _nodes[_n*_n-1]; if (last->dist == INT_MAX) { return -1; } else { return last->dist; } } }; int main(){ int n; cin >> n; map, int > results; for (int i=1; i, int>:: iterator it = results.find(make_pair(i,j)); cout << it->second << " "; } cout << endl; } return 0; }