import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; import java.awt.Point; import java.util.Comparator; import java.util.PriorityQueue; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); solve(n); } public static void solve(int n){ int[][] solution = new int[n][n]; for(int i = 1; i Q; private int n; private int t1; //traversalsize private int t2; Graph(int n, int t1, int t2){ this.n = n; this.g = new int[n][n]; if(t2>t1){ this.t1 = t2; this.t2 = t1; }else{ this.t1 = t1; this.t2 = t2; } PointComparator comparator = new PointComparator(g); this.Q = new PriorityQueue<>(n*n, comparator); } public void bfs(Point p){ int level = 1; //enque out point Q.add(p); g[p.x][p.y] = level; //while the queue is not empty while(!Q.isEmpty()){ //dequeue element p = Q.poll(); //set level level = g[p.x][p.y]+1; //and enqueue adjacents addValidSpacesToPriorityQueue(p, level); } } public void addValidSpacesToPriorityQueue(Point p, int priority){ //System.out.println(p.toString()); //calculate the 8 potential next spaces //add the valid ones to the queue in starting with max xy sum (bottom right) addBottomRight(p, priority); addBottomLeft(p, priority); addTopRight(p, priority); addTopLeft(p, priority); //System.out.println(Q.size()); } //adds to Q if no priority in the graph private void addIfNoPrioritySet(Point p, int priority){ if(g[p.x][p.y]==0){ g[p.x][p.y]=priority; Q.add(p); } } private void addTopLeft(Point p, int priority){ if(p.x - t2 >= 0 && p.y - t1 >= 0){ addIfNoPrioritySet(new Point(p.x - t2, p.y - t1), priority); } if(t1 == t2){ return; } if(p.x - t1 >= 0 && p.y - t2 >= 0){ addIfNoPrioritySet(new Point(p.x - t1, p.y - t2), priority); } } private void addTopRight(Point p, int priority){ if(p.x - t2 >= 0 && p.y + t1 < n){ addIfNoPrioritySet(new Point(p.x - t2, p.y + t1), priority); } if(t1 == t2){ return; } if(p.x - t1 >= 0 && p.y + t2 < n){ addIfNoPrioritySet(new Point(p.x - t1, p.y + t2), priority); } } private void addBottomLeft(Point p, int priority){ if((p.x + t1) < n && (p.y - t2) >= 0){ addIfNoPrioritySet(new Point(p.x + t1, p.y - t2), priority); } if(t1 == t2){ return; } if((p.x + t2) < n && (p.y - t1) >= 0){ addIfNoPrioritySet(new Point(p.x + t2, p.y - t1), priority); } } private void addBottomRight(Point p, int priority){ if((p.x + t2) < n && (p.y + t1) < n){ addIfNoPrioritySet(new Point(p.x + t2, p.y + t1), priority); } if(t1 == t2){ return; } if((p.x + t1) < n && (p.y + t2) < n ){ addIfNoPrioritySet(new Point(p.x + t1, p.y + t2), priority); } } public String printGraph(){ String s =""; for(int i=0;i< g.length; i++){ for(int j=0; j { private int[][] g; public PointComparator(int[][] graph) { this.g = graph; } @Override public int compare(Point o1, Point o2) { //look in the graph and return the priority from there return g[o1.x][o1.y] - g[o2.x][o2.y]; } }