#include <iostream> #include <queue> #include <cstring> using namespace std; int bfs(int r,int t,int n) { //ok we have NxN grid //we start from 0,0 and move current pos +-x and +-y // cout<<"doing for knight("<<r<<","<<t<<")"<<endl; int x=0,y=0; queue<pair<int,int> > q; int dist[n][n]; memset(dist,0,sizeof(int)*n*n); int visited[n][n]; memset(visited,0,sizeof(int)*n*n); //cout<<visited[2][2]<<" check"<<endl; dist[x][y]=0; q.push(pair<int,int>(x,y)); visited[0][0]=1; while(!q.empty()) { //now set distances of x+-i and y+-i to q.front +1 pair<int,int> pos = q.front(); //cout<<"q.front() is-"<<q.front().first<<","<<q.front().second<<endl; int newx[2],newy[2]; newx[0]=pos.first +r; newx[1]=pos.first -r; newy[0]=pos.second+t; newy[1]=pos.second-t; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { // cout<<"pairs formed - ("<<newx[i]<<","<<newy[j]<<")"<<endl; if(newx[i]>=0 && newx[i]<n && newy[j]>=0 && newy[j]<n &&visited[newx[i]][newy[j]]==0) { dist[newx[i]][newy[j]]=1+dist[pos.first][pos.second]; dist[newy[j]][newx[i]]=1+dist[pos.first][pos.second]; // cout<<"distance of ("<<newx[i]<<","<<newy[j]<<") is"<<dist[newx[i]][newy[j]]<<endl; // cout<<"pushed pairs are-"<<newx[i]<<","<<newy[j]<<endl; q.push(pair<int,int>(newx[i],newy[j])); q.push(pair<int,int>(newy[j],newx[i])); //set them as visited visited[newx[i]][newy[j]]=1; visited[newy[j]][newx[i]]=1; } } } q.pop(); } if(dist[n-1][n-1]==0)return -1; else return dist[n-1][n-1]; } int main() { //use bfs to find the shortest path int n; cin>>n; //now for each pair i,j will have to find out the paths for(int i=1;i<n;i++) { for(int j=1;j<n;j++) { //now main logic goes here,phew :| cout<<bfs(i,j,n)<<" "; } cout<<endl; } return 0; }