QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#98793	#5605. A-Mazing Puzzle	Nicolas125841	RE	100ms	43576kb	Java11	6.3kb	2023-04-20 06:22:05	2023-04-20 06:22:06

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-04-20 06:22:06]
评测

测评结果：RE
用时：100ms
内存：43576kb

查看

[2023-04-20 06:22:05]
提交

answer

import java.io.*;
import java.util.*;

public class ama {

	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int c = Integer.parseInt(st.nextToken()), r = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken())-1;
		
		st = new StringTokenizer(br.readLine());
		
		Robot r1 = new Robot(Integer.parseInt(st.nextToken())-1, r-Integer.parseInt(st.nextToken()), st.nextToken().charAt(0));
		Robot r2 = new Robot(Integer.parseInt(st.nextToken())-1, r-Integer.parseInt(st.nextToken()), st.nextToken().charAt(0));
						
		char[] dirs = new char[] {'N', 'E', 'S', 'W'};
		int angle = 0, r1d = 0, r2d = 0;
		
		for(int i = 0; i < 4; i++) {
			if(dirs[i] == r1.d)
				r1d = i;
			if(dirs[i] == r2.d)
				r2d = i;
		}
		
		if(r1d <= r2d)
			angle = r2d-r1d;
		else
			angle = 4+r2d-r1d;
				
		int[][] block = new int[r+1][c];
		
		st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		
		for(int i = 0; i < n; i++) {
			int blockc = Integer.parseInt(st.nextToken())-1, blockr = r-Integer.parseInt(st.nextToken());
			
			block[blockr][blockc] |= 1;
			block[blockr-1][blockc] |= 4;						
		}
		
		st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		
		for(int i = 0; i < n; i++) {
			int blockc = Integer.parseInt(st.nextToken())-1, blockr = r-Integer.parseInt(st.nextToken());
			
			block[blockr][blockc] |= 2;
			block[blockr][blockc+1] |= 8;						
		}
		
		for(int i = 0; i <= r; i++) {
			block[i][0] |= 8;
			block[i][c-1] |= 2;
		}
		
		for(int i = 0; i < c; i++) {
			block[0][i] |= 1;
			block[r][i] |= 4;
			if(i != e) {
				block[r-1][i] |= 4;
				block[r][i] |= 1;
			}
		}
			
		PriorityQueue<Dist> pq = new PriorityQueue<Dist>(new Comparator<Dist>() {
			@Override
			public int compare(Dist a, Dist b) {
				// TODO Auto-generated method stub
				return Integer.compare(a.d, b.d);
			}			
		});
		
		int[][] dist = new int[r+1][c];
		int[] dr = new int[] {-1, 0, 1, 0};
		int[] dc = new int[] {0, 1, 0, -1};
		
		for(int i = 0; i <= r; i++)
			for(int j = 0; j < c; j++)
				dist[i][j] = 1000000;
		
		pq.add(new Dist(r, e, 0));
		
		dist[r][e] = 0;
		
		while(!pq.isEmpty()) {
			Dist cur = pq.poll();
			
			if(dist[cur.r][cur.c] == cur.d) {
				for(int i = 0; i < 4; i++) {
					if(((block[cur.r][cur.c]>>i)&1) == 1 || dist[cur.r+dr[i]][cur.c+dc[i]] <= cur.d+1)
						continue;
					
					dist[cur.r+dr[i]][cur.c+dc[i]] = cur.d+1;
					pq.add(new Dist(cur.r+dr[i], cur.c+dc[i], cur.d+1));
				}
			}
		}
		
		if(r == 50)
			System.out.println("HIT");
				
		int[][][] cost = new int[r+1][c][2];
		
		for(int i = 0; i <= r; i++)
			for(int j = 0; j < c; j++)
				cost[i][j][0] = cost[i][j][1] = 1000000;
		
		PriorityQueue<State> spq = new PriorityQueue<State>(new Comparator<State>() {
			@Override
			public int compare(ama.State a, ama.State b) {
				// TODO Auto-generated method stub
				if(a.d + dist[a.r2][a.c2] == b.d + dist[b.r2][b.c2])
					return Integer.compare(a.bumps,b.bumps);				
				
				return Integer.compare(a.d + dist[a.r2][a.c2], b.d + dist[b.r2][b.c2]);
			}						
		});	
		
		spq.add(new State(r1.r, r1.c, r2.r, r2.c, 0, 0));
		
		cost[r1.r][r1.c][0] = dist[r2.r][r2.c];
		cost[r1.r][r1.c][1] = 0;
						
		while(!spq.isEmpty()) {
			State cur = spq.poll();
			
			if(cost[cur.r1][cur.c1][0] < cur.d + dist[cur.r2][cur.c2])
				continue;
			else if(cost[cur.r1][cur.c1][0] == cur.d + dist[cur.r2][cur.c2])
				if(cost[cur.r1][cur.c1][1] < cur.bumps)
					continue;
						
			for(int i = 0; i < 4; i++) {
				if(((block[cur.r1][cur.c1]>>i)&1) == 1) {
					if(((block[cur.r2][cur.c2]>>((i+angle)%4))&1)==1 || (cur.r2 == r && cur.c2 == e))
						continue;
					
					int nr1 = cur.r1, nc1 = cur.c1;
					int nr2 = cur.r2 + dr[(i+angle)%4], nc2 = cur.c2 + dc[(i+angle)%4];
					int bump = 1;
					
					if(nr1 == nr2 && nc1 == nc2 && !(cur.r2 == r && cur.c2 == e))
						continue;
					
					if(cost[nr1][nc1][0] > cur.d + 1 + dist[nr2][nc2]) {
						cost[nr1][nc1][0] = cur.d + 1 + dist[nr2][nc2];
						cost[nr1][nc1][1] = cur.bumps + bump;
						
						spq.add(new State(nr1, nc1, nr2, nc2, cur.bumps+bump, cur.d + 1));
					}else if(cost[nr1][nc1][0] == cur.d + 1 + dist[nr2][nc2] && cost[nr1][nr2][1] > cur.bumps + bump) {
						cost[nr1][nc1][0] = cur.d + 1 + dist[nr2][nc2];
						cost[nr1][nc1][1] = cur.bumps + bump;
						
						spq.add(new State(nr1, nc1, nr2, nc2, cur.bumps+bump, cur.d + 1));
					}					
				}else {				
					int nr1 = cur.r1 + dr[i], nc1 = cur.c1 + dc[i];
					int nr2 = cur.r2 + dr[(i+angle)%4], nc2 = cur.c2 + dc[(i+angle)%4];
					int bump = 0;
										
					if(((block[cur.r2][cur.c2]>>((i+angle)%4))&1)==1) {
						if(!(cur.r2 == r && cur.c2 == e))
							bump = 1;
						
						nr2 = cur.r2;
						nc2 = cur.c2;
					}
					
					if(nr1 == nr2 && nc1 == nc2 && !(cur.r2 == r && cur.c2 == e))
						continue;
					
					if(cost[nr1][nc1][0] > cur.d + 1 + dist[nr2][nc2]) {
						cost[nr1][nc1][0] = cur.d + 1 + dist[nr2][nc2];
						cost[nr1][nc1][1] = cur.bumps + bump;
						
						spq.add(new State(nr1, nc1, nr2, nc2, cur.bumps+bump, cur.d + 1));
					}else if(cost[nr1][nc1][0] == cur.d + 1 + dist[nr2][nc2] && cost[nr1][nr2][1] > cur.bumps + bump) {
						cost[nr1][nc1][0] = cur.d + 1 + dist[nr2][nc2];
						cost[nr1][nc1][1] = cur.bumps + bump;
						
						spq.add(new State(nr1, nc1, nr2, nc2, cur.bumps+bump, cur.d + 1));
					}
				}
			}
		}
		
		pw.println(cost[r][e][0] + " " + cost[r][e][1]);
		pw.close();
	}
	
	static class State{		
		int r1, c1, r2, c2, bumps, d;
		
		public State(int r1, int c1, int r2, int c2, int b, int d) {
			this.r1 = r1;
			this.c1 = c1;
			this.r2 = r2;
			this.c2 = c2;
			this.bumps = b;
			this.d = d;
		}
	}
	
	static class Dist{
		int r, c, d;
		
		public Dist(int r, int c, int d) {
			this.r = r;
			this.c = c;
			this.d = d;
		}
	}
	
	static class Robot{
		int r, c;
		char d;
		
		public Robot(int c, int r, char d) {
			this.r = r;
			this.c = c;
			this.d = d;
		}
	}
}

源文件, 语言: Java11

详细

Test #1:

score: 100

Accepted

time: 100ms

memory: 43576kb

input:

7 4 4
3 2 S 6 3 S
6 1 1 1 2 1 3 2 3 5 1 5 3
11 2 1 3 1 3 2 5 2 6 2 2 3 4 3 5 3 6 3 3 4 6 4

output:

8 1

result:

ok single line: '8 1'

Test #2:

score: 0

Accepted

time: 90ms

memory: 41136kb

input:

3 4 2
1 3 S 3 2 S
1 3 3
5 1 1 2 1 1 2 1 3 2 3

output:

7 2

result:

ok single line: '7 2'

Test #3:

score: -100

Runtime Error

input:

50 50 4
15 28 W 9 43 E
49 11 47 42 33 3 4 36 49 21 21 15 34 43 5 32 35 3 21 7 1 40 4 22 44 11 40 46 43 13 26 32 6 44 25 31 46 26 7 45 4 18 10 10 21 3 20 31 8 34 40 42 1 48 43 18 17 9 39 17 2 48 25 39 35 45 43 8 2 22 17 6 46 33 1 38 6 28 25 29 32 45 12 11 20 8 48 14 9 2 24 45 38 1 20 34 5 46 24
50 13...

output:

HIT