QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #98963 | #5605. A-Mazing Puzzle | Nicolas125841 | TL | 127ms | 54996kb | Java11 | 7.3kb | 2023-04-21 03:07:12 | 2023-04-21 03:07:17 |
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 * c + j][k * c + l][0] = cost[i * c + j][k * c + l][1] = 1000000;
PriorityQueue<int[]> spq = new PriorityQueue<int[]>(new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
// TODO Auto-generated method stub
if(a[5] + dist[a[2]][a[3]] == b[5] + dist[b[2]][b[3]])
return Integer.compare(a[4], b[4]);
return Integer.compare(a[5] + dist[a[2]][a[3]], b[5] + dist[b[2]][b[3]]);
}
});
spq.add(new int[] {r1.r, r1.c, r2.r, r2.c, 0, 0});
cost[r1.r*c+r1.c][r2.r*c+r2.c][0] = dist[r2.r][r2.c];
cost[r1.r*c+r1.c][r2.r*c+r2.c][1] = 0;
block[r][e] = 15;
//try {
while(!spq.isEmpty()) {
int[] cur = spq.poll();
//if(cur.c1 >= 50 || cur.c2 >= 50 || cur.r1 >= 50 || cur.r2 >= 50)
//System.out.println("ISSUE1");
if(cost[cur[0]*c+cur[1]][cur[2]*c+cur[3]][0] < cur[5] + dist[cur[2]][cur[3]])
continue;
else if(cost[cur[0]*c+cur[1]][cur[2]*c+cur[3]][0] == cur[5] + dist[cur[2]][cur[3]])
if(cost[cur[0]*c+cur[1]][cur[2]*c+cur[3]][1] < cur[4])
continue;
for(int i = 0; i < 4; i++) {
if(((block[cur[0]][cur[1]]>>i)&1) == 1) {
if(((block[cur[2]][cur[3]]>>((i+angle)%4))&1)==1 || (cur[2] == r && cur[3] == e))
continue;
int nr1 = cur[0], nc1 = cur[1];
int nr2 = cur[2] + dr[(i+angle)%4], nc2 = cur[3] + dc[(i+angle)%4];
int bump = (cur[0] == r && cur[1] == e) ? 0 : 1;
if(nr1 == nr2 && nc1 == nc2 && !(cur[2] == r && cur[3] == e))
continue;
//if(nc2 >= 50 || nc1 >= 50 || nr1 >= 50 || nr2 >= 50)
//System.out.println("ISSUE2");
if(cost[nr1*c+nc1][nr2*c+nc2][0] > cur[5] + 1 + dist[nr2][nc2]) {
cost[nr1*c+nc1][nr2*c+nc2][0] = cur[5] + 1 + dist[nr2][nc2];
cost[nr1*c+nc1][nr2*c+nc2][1] = cur[4] + bump;
spq.add(new int[] {nr1, nc1, nr2, nc2, cur[4] + bump, cur[5] + 1});
}else if(cost[nr1*c+nc1][nr2*c+nc2][0] == cur[5] + 1 + dist[nr2][nc2] && cost[nr1*c+nc1][nr2*c+nc2][1] > cur[4] + bump) {
cost[nr1*c+nc1][nr2*c+nc2][0] = cur[5] + 1 + dist[nr2][nc2];
cost[nr1*c+nc1][nr2*c+nc2][1] = cur[4] + bump;
spq.add(new int[] {nr1, nc1, nr2, nc2, cur[4] + bump, cur[5] + 1});
}
}else {
int nr1 = cur[0] + dr[i], nc1 = cur[1] + dc[i];
int nr2 = cur[2] + dr[(i+angle)%4], nc2 = cur[3] + dc[(i+angle)%4];
int bump = 0;
if(((block[cur[2]][cur[3]]>>((i+angle)%4))&1)==1) {
if(!(cur[2] == r && cur[3] == e))
bump = 1;
nr2 = cur[2];
nc2 = cur[3];
}
//if(nc2 >= 50 || nc1 >= 50 || nr1 >= 50 || nr2 >= 50)
//System.out.println("ISSUE3");
if(nr1 == nr2 && nc1 == nc2 && !(cur[2] == r && cur[3] == e))
continue;
if(cost[nr1*c+nc1][nr2*c+nc2][0] > cur[5] + 1 + dist[nr2][nc2]) {
cost[nr1*c+nc1][nr2*c+nc2][0] = cur[5] + 1 + dist[nr2][nc2];
cost[nr1*c+nc1][nr2*c+nc2][1] = cur[4] + bump;
spq.add(new int[] {nr1, nc1, nr2, nc2, cur[4] + bump, cur[5] + 1});
}else if(cost[nr1*c+nc1][nr2*c+nc2][0] == cur[5] + 1 + dist[nr2][nc2] && cost[nr1*c+nc1][nr2*c+nc2][1] > cur[4] + bump) {
cost[nr1*c+nc1][nr2*c+nc2][0] = cur[5] + 1 + dist[nr2][nc2];
cost[nr1*c+nc1][nr2*c+nc2][1] = cur[4] + bump;
spq.add(new int[] {nr1, nc1, nr2, nc2, cur[4] + bump, cur[5] + 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*c+e][i*c+j][0] < mina) {
mina = cost[r*c+e][i*c+j][0];
minb = cost[r*c+e][i*c+j][1];
}else if(cost[r*c+e][i*c+j][0] == mina && cost[r*c+e][i*c+j][1] < minb) {
mina = cost[r*c+e][i*c+j][0];
minb = cost[r*c+e][i*c+j][1];
}
}
}
pw.println(mina + " " + minb);
pw.close();
}
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;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 127ms
memory: 54996kb
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: 106ms
memory: 54588kb
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...