Untitled
unknown
plain_text
2 years ago
2.5 kB
4
Indexable
package MarioClimb; import java.util.Scanner; class MyQueue{ private int maxSize; private int[] array; private int input; private int output; public MyQueue(int maxSize) { this.maxSize = maxSize; array=new int[maxSize]; this.input = -1; this.output = -1; } public void push(int x){ input++; array[input]=x; } public int pop() { output++; return this.array[output]; } public int peek() { return this.array[output]; } public boolean isEmpty(){ if(input==output){ return true; } return false; } public void reset(){ this.input=-1; this.output=-1; } } public class test { static int N,M; static int x=0,y=0; static int x1=0,y1=0; static int h=0; static int[][] matrix=new int[100][100]; static int[][] visit=new int[100][100]; static int[] dx={0,-1,0,1}; static int[] dy={-1,0,1,0}; static MyQueue queueX=new MyQueue(1000000); static MyQueue queueY=new MyQueue(1000000); static void reset(){ for(int i=0;i<N;i++){ for(int j=0;j<M;j++){ visit[i][j]=0; } } } static void BFS(){ queueX.reset(); queueY.reset(); queueX.push(x); queueY.push(y); visit[x][y]=1; while(!queueX.isEmpty()){ int xx=queueX.pop(); int yy=queueY.pop(); for(int i=0;i<4;i++){ int r=xx+dx[i]; int c=yy+dy[i]; if(r<0 ||r>=N || c<0 || c>=M) continue; if(r==x1 && c==y1){ visit[x1][y1]=1; return; } if(matrix[r][c]==1 && visit[r][c]==0){ visit[r][c]=1; queueX.push(r); queueY.push(c); } else if((dx[i]==-1 ||dx[i]==1 )&&matrix[r][c]==0){ for(int m=1;m<=h;m++){ r=xx+m*dx[i]; if(r<0 ||r>=N || c<0 || c>=M) continue; if(r==x1 && c==y1){ visit[x1][y1]=1; return; } if(matrix[r][c]==1 && visit[r][c]==0){ visit[r][c]=1; queueX.push(r); queueY.push(c); } } } } } } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int tc=scanner.nextInt(); for(int i=0;i<tc;i++){ N=scanner.nextInt(); M=scanner.nextInt(); for(int j=0;j<N;j++ ){ for(int k=0;k<M;k++){ matrix[j][k]=scanner.nextInt(); if(matrix[j][k]==2){ x=j; y=k; } if(matrix[j][k]==3){ x1=j; y1=k; } } } for(int j=1;j<N;j++){ h=j; reset(); BFS(); if(visit[x1][y1]==1){ break; } } System.out.println("Case #"+(i+1)); System.out.println(h); } } }
Editor is loading...