#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <string> #include <bitset> #include <cstdio> #include <limits> #include <vector> #include <climits> #include <cstring> #include <cstdlib> #include <fstream> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; struct Node { int r,c; Node(int _r, int _c): r(_r), c(_c) {} }; int minDist(int n, int a, int b, vector<vector<int>>& grid) { int i,j; vector<int> oneMove(2); vector<vector<int>> moves(8,oneMove); int m[]={-1,1}; for (int i=0;i<2;i++) for(int j=0;j<2;j++) { oneMove[0]=m[i]*a; oneMove[1]=m[j]*b; moves.push_back(oneMove); swap(oneMove[0],oneMove[1]); moves.push_back(oneMove); } for (i=0;i<n;i++) for(j=0;j<n;j++) grid[i][j]=n*n+1; grid[0][0] = 0; Node cur(0,0); queue<Node> nodeQ; nodeQ.push(cur); while (nodeQ.empty()==false) { cur = nodeQ.front(); nodeQ.pop(); for (int i=0;i<moves.size();i++) { Node newNode(cur.r + moves[i][0],cur.c + moves[i][1]); if (newNode.r<0 || newNode.r>=n || newNode.c<0||newNode.c>=n) continue; if ( grid[newNode.r][newNode.c] > grid[cur.r][cur.c]+1) { grid[newNode.r][newNode.c]=grid[cur.r][cur.c]+1; if (newNode.r==n-1&&newNode.c==n-1) return grid[n-1][n-1]; nodeQ.push(newNode); } } } return -1; } int main(){ int n; cin >> n; // your code goes here int a,b; vector<int> oneRow(n); vector< vector<int> > grid(n,oneRow); for (a=1;a<n;a++) { for (b=1;b<n;b++) { if ( b>1) cout<<" "; cout<<minDist(n,a,b,grid); } cout<<endl; } return 0; }