#include #include #include #include using namespace std; void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { vector < vector < pair > > g(n*n); vector< vector > v(n, vector(n)); int r = 0; for (int i = 0; i= 0) { g[cur].push_back(make_pair(v[i][j-2], "R")); g[v[i][j-2]].push_back(make_pair(cur, "L")); } if (j+1 < n && i-2 >= 0) { g[cur].push_back(make_pair(v[i-2][j+1], "UR")); g[v[i-2][j+1]].push_back(make_pair(cur, "UL")); } if (j-1 >= 0 && i-2 >= 0) { g[cur].push_back(make_pair(v[i-2][j-1], "UL")); g[v[i-2][j-1]].push_back(make_pair(cur, "UR")); } if (j+1 < n && i+2 < n) { g[cur].push_back(make_pair(v[i+2][j+1], "LL")); g[v[i+2][j+1]].push_back(make_pair(cur, "LR")); } if (j-1 >= 0 && i+2 < n) { g[cur].push_back(make_pair(v[i+2][j-1], "LR")); g[v[i+2][j-1]].push_back(make_pair(cur, "LL")); } } } int s = v[i_start][j_start]; int to = v[i_end][j_end]; queue q; q.push (s); vector used (n*n); vector d (n*n), p (n*n); used[s] = true; p[s] = -1; while (!q.empty()) { int v = q.front(); q.pop(); for (size_t i=0; i path; for (int v=to; v!=-1; v=p[v]) path.push_back (v); reverse (path.begin(), path.end()); int pre = s; cout << path.size()-1 << endl; for (size_t i=1; i> n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }