Untitled
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