Untitled

 avatar
unknown
plain_text
9 months ago
2.7 kB
10
Indexable
package practice1;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class FastRobot {
	public static int MAX = 1000000;
	public static int[] A = new int[MAX];
	
	public static int front = 0;
	public static int rear = -1;
	
	public static int[] dx = {0, 0, -1, 1};
	public static int[] dy = {-1, 1, 0, 0};
	
	public static class Queue {
		
		public Queue() {
			// TODO Auto-generated constructor stub
		}
		
		public boolean isEmpty () {
			if (front > rear) return true;
			else return false;
		}
		
		public boolean isFull() {
			if (rear - front == MAX - 1) return true;
			else return false;
		}
		
		public void enqueue(int a) {
			if(!isFull()) {
				rear++;
				A[rear] = a;
			}
		}
		
		public int dequeue() {
			if(!isEmpty()) {
				front++;
				return A[front-1];
			}
			return -1;
		}
		
		public int peek() {
			return A[front];
		}
		
		public void reset() {
			front = 0;
			rear = -1;
		}
		public int size() {
			if(!isEmpty()){
				return rear - front + 1;
			}
			return 0;
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("C:/Users/srv_training/workspace/testabc/src/input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int t1 = 1; t1 <= t; t1++) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int[][] map = new int[m][n];
			int[][] bfs = new int[m][n];
			int starty = sc.nextInt() - 1;
			int startx = sc.nextInt() - 1;
			int endy = sc.nextInt() - 1;
			int endx = sc.nextInt() - 1;
			int answer = 0;
			int change = 0;
			sc.nextLine();
			for (int i = 0; i < m; i++) {
				String s = sc.nextLine();
				for (int j = 0; j < n; j++) {
					map[i][j] = s.charAt(j) - '0';
				}
			}
			Queue queue = new Queue();
			bfs[startx][starty] = 1;
			queue.enqueue(startx);
			queue.enqueue(starty);
			queue.enqueue(change);
			
			while(!queue.isEmpty()) {
				startx = queue.dequeue();
				starty = queue.dequeue();
				change = queue.dequeue();
				for (int k = 0; k < 4; k++) {
					int nextx = startx + dx[k];
					int nexty = starty + dy[k];
					
					while(nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && map[nextx][nexty] == 0) {
//						if (nextx == endx && nexty == endy && (answer == 0 || answer > change + 1)) {
//							answer = change + 1;
//						}
						if (bfs[nextx][nexty] == 0) {
							bfs[nextx][nexty] = change + 1;
							queue.enqueue(nextx);
							queue.enqueue(nexty);
							queue.enqueue(change+1);
						}
						nextx += dx[k];
						nexty += dy[k];
					}
				}
			}
			
			System.out.println(bfs[endx][endy] - 1);
		}
		sc.close();
	}
}
Editor is loading...
Leave a Comment