oj.uz

답안 #348070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348070 2021-01-14T06:47:01 Z KachiTachi Tracks in the Snow (BOI13_tracks) Java 11
84.6875 / 100
 2000 ms 408948 KB 
import java.io.*;
import java.util.*;

class triple {
    public int r;
    public int c;
    public int depth;
    
    public triple (int r, int c, int depth) {
        this.r = r;
        this.c = c;
        this.depth = depth;
    }
    
    public String toString() {
        return "(" + r + ", " + c + ", depth: " + depth + ")"; 
    }
}

public class tracks {
    
    public static int H;
    public static int W;
    public static char[][] snow;
    public static int[][] deltas = new int[][] {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
	public static void main (String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		snow =  new char[H][W];
		
		for (int r = 0; r < H; r++) {
		    String line = br.readLine();
		    for (int c = 0; c < W; c++) {
		        snow[r][c] = line.charAt(c);
		    }
		}
		
//		System.out.println(Arrays.deepToString(snow));
		
		PrintWriter pw = new PrintWriter(System.out);
		pw.println(bfs());
		pw.close();
	}
	
	public static int bfs() {
	    int numAnimals = 1;
	    boolean[][] seen = new boolean[H][W];
	    Deque<triple> frontier = new ArrayDeque<>();
	    frontier.addFirst(new triple(0, 0, numAnimals));
	    
	    while (!frontier.isEmpty()) {
	        triple curTriple = frontier.removeFirst();
	        int r = curTriple.r;
	        int c = curTriple.c;
	        int depth = curTriple.depth;
	        
	        if (seen[r][c]) {
	            continue;
	        }
	        
	        seen[r][c] = true;
	        numAnimals = Math.max(numAnimals, depth);
	        
	        char curAnimal = snow[r][c];
	        for (int[] delt : deltas) {
	            int newR = r + delt[0];
	            int newC = c + delt[1];
	            if (newR >= 0 && newR < H && newC >= 0 && newC < W) {
	                if (seen[newR][newC]) {
	                    continue;
	                }
	                char newAnimal = snow[newR][newC];
	                if (newAnimal == 'R' || newAnimal == 'F') {
	                    if (newAnimal == curAnimal) {
	                        frontier.addFirst(new triple(newR, newC, depth));
	                    } else {
	                        frontier.addLast(new triple(newR, newC, depth + 1));
	                    }
	                }
	            }
	        }
	    }
	    return numAnimals;
	}
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 314 ms 16168 KB Output is correct
2 Correct 72 ms 8540 KB Output is correct
3 Correct 75 ms 8556 KB Output is correct
4 Correct 298 ms 16848 KB Output is correct
5 Correct 197 ms 13116 KB Output is correct
6 Correct 70 ms 8556 KB Output is correct
7 Correct 79 ms 8544 KB Output is correct
8 Correct 104 ms 10820 KB Output is correct
9 Correct 101 ms 10204 KB Output is correct
10 Correct 226 ms 13280 KB Output is correct
11 Correct 271 ms 14560 KB Output is correct
12 Correct 209 ms 14688 KB Output is correct
13 Correct 192 ms 12896 KB Output is correct
14 Correct 194 ms 12880 KB Output is correct
15 Correct 250 ms 15456 KB Output is correct
16 Correct 299 ms 16096 KB Output is correct
17 Correct 238 ms 15312 KB Output is correct
18 Correct 285 ms 16692 KB Output is correct

Subtask #2
54.6875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 12740 KB Output is correct
2 Correct 337 ms 19444 KB Output is correct
3 Correct 783 ms 85600 KB Output is correct
4 Correct 359 ms 30944 KB Output is correct
5 Correct 627 ms 57268 KB Output is correct
6 Execution timed out 2115 ms 270304 KB Time limit exceeded
7 Correct 258 ms 12916 KB Output is correct
8 Correct 204 ms 12776 KB Output is correct
9 Correct 289 ms 14176 KB Output is correct
10 Correct 234 ms 12128 KB Output is correct
11 Correct 202 ms 12508 KB Output is correct
12 Correct 187 ms 12128 KB Output is correct
13 Correct 333 ms 19408 KB Output is correct
14 Correct 257 ms 17612 KB Output is correct
15 Correct 255 ms 17616 KB Output is correct
16 Correct 273 ms 16608 KB Output is correct
17 Correct 514 ms 33232 KB Output is correct
18 Correct 386 ms 32720 KB Output is correct
19 Correct 357 ms 31032 KB Output is correct
20 Correct 342 ms 29520 KB Output is correct
21 Correct 576 ms 58228 KB Output is correct
22 Correct 614 ms 57568 KB Output is correct
23 Correct 778 ms 51320 KB Output is correct
24 Correct 579 ms 58080 KB Output is correct
25 Correct 943 ms 85216 KB Output is correct
26 Execution timed out 2105 ms 408948 KB Time limit exceeded
27 Execution timed out 2106 ms 358140 KB Time limit exceeded
28 Execution timed out 2084 ms 270368 KB Time limit exceeded
29 Execution timed out 2111 ms 249728 KB Time limit exceeded
30 Execution timed out 2100 ms 315616 KB Time limit exceeded
31 Correct 1677 ms 68704 KB Output is correct
32 Execution timed out 2121 ms 351120 KB Time limit exceeded