Untitled

 avatar
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...