QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #98958 | #5605. A-Mazing Puzzle | Nicolas125841 | TL | 140ms | 53892kb | Java11 | 7.5kb | 2023-04-21 02:36:15 | 2023-04-21 02:36:16 |
Judging History
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));
}
}
}
int[][][][][] cost = new int[r+1][c][r+1][c][2];
for(int i = 0; i <= r; i++)
for(int j = 0; j < c; j++)
for(int k = 0; k <= r; k++)
for(int l = 0; l < c; l++)
cost[i][j][k][l][0] = cost[i][j][k][l][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][r2.r][r2.c][0] = dist[r2.r][r2.c];
cost[r1.r][r1.c][r2.r][r2.c][1] = 0;
block[r][e] = 15;
//try {
while(!spq.isEmpty()) {
State cur = spq.poll();
//if(cur.c1 >= 50 || cur.c2 >= 50 || cur.r1 >= 50 || cur.r2 >= 50)
//System.out.println("ISSUE1");
if(cost[cur.r1][cur.c1][cur.r2][cur.c2][0] < cur.d + dist[cur.r2][cur.c2])
continue;
else if(cost[cur.r1][cur.c1][cur.r2][cur.c2][0] == cur.d + dist[cur.r2][cur.c2])
if(cost[cur.r1][cur.c1][cur.r2][cur.c2][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 = (cur.r1 == r && cur.c1 == e) ? 0 : 1;
if(nr1 == nr2 && nc1 == nc2 && !(cur.r2 == r && cur.c2 == e))
continue;
//if(nc2 >= 50 || nc1 >= 50 || nr1 >= 50 || nr2 >= 50)
//System.out.println("ISSUE2");
if(cost[nr1][nc1][nr2][nc2][0] > cur.d + 1 + dist[nr2][nc2]) {
cost[nr1][nc1][nr2][nc2][0] = cur.d + 1 + dist[nr2][nc2];
cost[nr1][nc1][nr2][nc2][1] = cur.bumps + bump;
spq.add(new State(nr1, nc1, nr2, nc2, cur.bumps+bump, cur.d + 1));
}else if(cost[nr1][nc1][nr2][nc2][0] == cur.d + 1 + dist[nr2][nc2] && cost[nr1][nc1][nr2][nc2][1] > cur.bumps + bump) {
cost[nr1][nc1][nr2][nc2][0] = cur.d + 1 + dist[nr2][nc2];
cost[nr1][nc1][nr2][nc2][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(nc2 >= 50 || nc1 >= 50 || nr1 >= 50 || nr2 >= 50)
//System.out.println("ISSUE3");
if(nr1 == nr2 && nc1 == nc2 && !(cur.r2 == r && cur.c2 == e))
continue;
if(cost[nr1][nc1][nr2][nc2][0] > cur.d + 1 + dist[nr2][nc2]) {
cost[nr1][nc1][nr2][nc2][0] = cur.d + 1 + dist[nr2][nc2];
cost[nr1][nc1][nr2][nc2][1] = cur.bumps + bump;
spq.add(new State(nr1, nc1, nr2, nc2, cur.bumps+bump, cur.d + 1));
}else if(cost[nr1][nc1][nr2][nc2][0] == cur.d + 1 + dist[nr2][nc2] && cost[nr1][nc1][nr2][nc2][1] > cur.bumps + bump) {
cost[nr1][nc1][nr2][nc2][0] = cur.d + 1 + dist[nr2][nc2];
cost[nr1][nc1][nr2][nc2][1] = cur.bumps + bump;
spq.add(new State(nr1, nc1, nr2, nc2, cur.bumps+bump, cur.d + 1));
}
}
}
}
//}catch(Exception ex) {
//System.out.println(ex.getLocalizedMessage());
//}
int mina = 1000000, minb = 1000000;
for(int i = 0; i <= r; i++) {
for(int j = 0; j < c; j++) {
if(cost[r][e][i][j][0] < mina) {
mina = cost[r][e][i][j][0];
minb = cost[r][e][i][j][1];
}else if(cost[r][e][i][j][0] == mina && cost[r][e][i][j][1] < minb) {
mina = cost[r][e][i][j][0];
minb = cost[r][e][i][j][1];
}
}
}
pw.println(mina + " " + minb);
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;
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 140ms
memory: 53892kb
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: 105ms
memory: 53016kb
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
Time Limit Exceeded
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...