codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
//quan tuong import java.util.Scanner; public class Solution { static int A[][]; static int kiux[]=new int[1000000]; static int kiuy[]=new int[1000000]; static int kius[]=new int[1000000]; static int l,r,s; static int trongso[][]; static boolean danhdau[][]; public static void main(String[] args) { //System.setIn(new FileInputStream("quantuong.txt")); Scanner sc=new Scanner(System.in); int T=sc.nextInt(); for (int t = 1; t <=T; t++) { int n=sc.nextInt(); int m=sc.nextInt(); int bdx=n-sc.nextInt(); int bdy=sc.nextInt()-1; int ktx=n-sc.nextInt(); int kty=sc.nextInt()-1; A=new int[n][n]; for (int i = 0; i < m; i++) { A[n-sc.nextInt()][sc.nextInt()-1]=1; } trongso=new int[n][n]; danhdau=new boolean[n][n]; l=-1;r=-1; push(bdx,bdy,0); while(l!=r){ pop(); int x=kiux[l]; int y=kiuy[l]; int s=kius[l]; int j=y; for (int i = x; i>=0&&j<A.length; i--) { if(A[i][j]==1) break; if(A[i][j]==0&&!danhdau[i][j]){ push(i, j, s+1); } if(A[i][j]==0&&danhdau[i][j]&&s+1<trongso[i][j]){ push(i, j, s+1); } j++; } j=y; for (int i = x; i>=0&&j>=0; i--) { if(A[i][j]==1) break; if(A[i][j]==0&&!danhdau[i][j]){ push(i, j, s+1); } if(A[i][j]==0&&danhdau[i][j]&&s+1<trongso[i][j]){ push(i, j, s+1); } j--; } j=y; for (int i = x; i<A.length&&j<A.length; i++) { if(A[i][j]==1) break; if(A[i][j]==0&&!danhdau[i][j]){ push(i, j, s+1); } if(A[i][j]==0&&danhdau[i][j]&&s+1<trongso[i][j]){ push(i, j, s+1); } j++; } j=y; for (int i = x; i<A.length&&j>=0; i++) { if(A[i][j]==1) break; if(A[i][j]==0&&!danhdau[i][j]){ push(i, j, s+1); } if(A[i][j]==0&&danhdau[i][j]&&s+1<trongso[i][j]){ push(i, j, s+1); } j--; } } System.out.println(trongso[ktx][kty]); } } static void push(int x,int y, int s){ kiux[++r]=x; kiuy[r]=y; kius[r]=s; danhdau[x][y]=true; trongso[x][y]=s; } static void pop(){ l++; } }
Private
[
?
]
Run code
Submit