#include #define scanI(n) scanf("%d", &n) #define scanL(n) scanf("%ld", &n) #define scanLL(n) scan("%lld", &n) #define scanII(a, b) scanf("%d %d", &a, &b) #define scanIII(a, b, c) scanf("%d %d %d", &a, &b, &c); #define printI(n) printf("%d", n) #define printII(a,b) printf("%d %d", a, b) #define PRINT(list) for(auto i : list) printf("%d ", i); printf("\n"); #define PRINTARR(ar_, n_) for(int i_=0; i_ #define PR pair #define LL long long #define MOD 1000000007 #define PI 3.142857 #define FORi(n) for(int i=0; i> adj(int n, pair v){ vector> list; int i = v.first, j = v.second; if(i-2 >= 0 && j-1 >= 0){ //UL list.push_back({i-2, j-1}); } if(i-2 >= 0 && j+1 < n){ //UR list.push_back({i-2, j+1}); } if(j + 2 < n){ //R list.push_back({i, j+2}); } if(i+2 < n && j+1 < n){ //LR list.push_back({i+2, j+1}); } if(i+2 < n && j-1 >= 0){ //LL list.push_back({i+2, j-1}); } if(j - 2 >= 0){ //L list.push_back({i, j-2}); } return list; /* printf("%d %d\n", i, j); for(auto v: list){ cout << v.first << ", " << v.second << " | "; } cout << "done" << endl;*/ } string move(pair p1, pair p2){ int si=p1.first, sj=p1.second; int ei=p2.first, ej=p2.second; if(si==ei && ej == (sj-2)) return "L"; if(si==ei && ej == (sj+2)) return "R"; if(ei==(si-2) && ej == (sj-1)) return "UL"; if(ei==(si-2) && ej == (sj+1)) return "UR"; if(ei==(si+2) && ej == (sj-1)) return "LL"; if(ei==(si+2) && ej == (sj+1)) return "LR"; return "NULL"; } void bfs(int n, int si, int sj, int ei, int ej){ bool visited[n][n]; pair parent[n][n]; for(int i=0; i> q; q.push({si, sj}); while(!q.empty()){ auto tp = q.front(); q.pop(); for(auto v: adj(n, tp)){ if(!visited[v.first][v.second]){ visited[v.first][v.second] = true; parent[v.first][v.second] = tp; //printf("%d %d -> parent : %d %d\n", v.first, v.second, tp.first, tp.second); q.push(v); } } } parent[si][sj] = {-1, -1}; pair cr = {ei, ej}; pair start_pair = {si, sj}; pair end_pair = {ei, ej}; pair null_pair = {-1, -1}; vector> path; path.push_back(cr); while(parent[cr.first][cr.second] != null_pair){ //printf("%d %d\n", cr.first, cr.second); path.push_back(parent[cr.first][cr.second]); cr = parent[cr.first][cr.second]; } if(path.front()==end_pair && path.back() == start_pair){ reverse(ALL(path)); printf("%d\n", path.size()-1); for(int i=1; i ei) || (si > ei && ci < ei)){ return "Impossible"; } else if((sj < ej && cj > ej) || (sj > ej && cj < ej)){ return "Impossible"; } else{ return path + min( ); } }*/