#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int dist(int n, int x, int y){ return (n-x-1)+(n-y-1); } /*int ezaf(int n, int x, int y, int a, int b, int moves, vector> &visited){ //if(x=0 && y>=0){ visited[x][y]=true; //} //int urg = 0; if((n-1)%(a+b)==0){ return 2*(n-1)/(a+b); } if(a==b && (n-1)%(a+b)!=0){ return INT_MAX; } if(x==n-1 && y==n-1){ return moves; } else if((n-a-1==x && n-b-1==y) || (n-b-1==x && n-a-1==y)){ return moves+1; } else if(moves>2*(n)){ return INT_MAX; } vector movez(8, INT_MAX); int c = max(a,b); if(x>=n-2*c && y>=n-2*c){ if((x+a)=0){ if(!visited[x+a][y-b]) movez[1]=(ezaf(n, x+a, y-b, a, b, moves+1, visited)); } if((x-a)>=0 && (y+b)=0){ if(!visited[x+b][y-a]) movez[4]=(ezaf(n, x+b, y-a, a, b, moves+1, visited)); } if((x-b)>=0 && (y+a)=0){ if(!visited[x+a][y-b]) movez[1]=dist(n,x+a,y-b); } if((x+b)=0){ if(!visited[x+b][y-a]) movez[4]=dist(n,x+b,y-a); } if((x-a)>=0 && (y+b)=0 && (y+a)=0 && (y-b)>=0){ if(!visited[x-a][y-b]) movez[6]=dist(n,x-a,y-b); } if((x-b)>=0 && (y-a)>=0){ if(!visited[x-b][y-a]) movez[7]=dist(n,x-b,y-a); } int min=INT_MAX, index; for(int i=0;i<8;++i){ if(movez[i]> visited(n,vector(n,false)); visited[0][0] = true; vector> dir; dir.push_back({a,b}); dir.push_back({b,a}); dir.push_back({a,-b}); dir.push_back({b,-a}); dir.push_back({-a,b}); dir.push_back({-b,a}); dir.push_back({ -a,-b}); dir.push_back({-b,-a}); queue> qq; qq.push({0,0,0}); while(!qq.empty()){ int x = qq.front()[0]; int y = qq.front()[1]; int moves = qq.front()[2]; qq.pop(); if(x==n-1 && y==n-1){ return moves; } for(int i=0;i<8;++i){ int xx = x+dir[i][0]; int yy = y+dir[i][1]; if((xx >= 0) && (xx < n) && (yy >= 0) && (yy < n) && !visited[xx][yy]){ visited[xx][yy] = true; qq.push({xx,yy,moves+1}); } } } if(!visited[n-1][n-1]) return -1; return 0; //return ezaf(n, 0, 0, a, b, 0, visited); } int main(){ int n; cin >> n; // your code goes here vector>> k; k.resize(n-1); for(int i=0;i> ans(n-1,vector(n-1,-1)); for(int i=0;in/2 && j+1>n/2) tmp = -1; else{ tmp = minmoves(n, k[i][j][0], k[i][j][1]); if(tmp==INT_MAX) tmp = -1; } ans[i][j]=tmp; } } /*for(int i=0;i