Submission #666560

#	Time	Username	Problem	Language	Result	Execution time	Memory
666560		achejakhang	Tracks in the Snow (BOI13_tracks)	Java	86.88 / 100	2103 ms	656992 KiB

tracks

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

public class tracks {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		
		StringTokenizer in = new StringTokenizer(br.readLine());
		int h = Integer.parseInt(in.nextToken()), w = Integer.parseInt(in.nextToken());
		int[][] grid = new int[h][w];
		for (int i=0; i< h; i++) {
			String s = br.readLine();
			for (int j =0; j< w; j++) grid[i][j] = s.charAt(j);
		}
		
		ArrayDeque<int[]> next = new ArrayDeque<>();
		next.addLast(new int[] {0,0,1});
		int maxV = 1;
		while (!next.isEmpty()) {
			int[] vals = next.removeFirst();
			int r = vals[0], c = vals[1], v = vals[2];
			maxV = Math.max(maxV, v);
			if (r < h-1 && grid[r+1][c] != '.') {
				if (grid[r+1][c]==grid[r][c]) {
					next.addFirst(new int[] {r+1,c,v});
				} else {
					next.addLast(new int[] {r+1,c,v+1});
				}
			}
			if (r > 0 && grid[r-1][c] != '.') {
				if (grid[r-1][c]==grid[r][c]) {
					next.addFirst(new int[] {r-1,c,v});
				} else {
					next.addLast(new int[] {r-1,c,v+1});
				}
			}
			if (c < w-1 && grid[r][c+1] != '.') {
				if (grid[r][c+1]==grid[r][c]) {
					next.addFirst(new int[] {r,c+1,v});
				} else {
					next.addLast(new int[] {r,c+1,v+1});
				}
			}
			if (c > 0 && grid[r][c-1] != '.') {
				if (grid[r][c-1]==grid[r][c]) {
					next.addFirst(new int[] {r,c-1,v});
				} else {
					next.addLast(new int[] {r,c-1,v+1});
				}
			}
			grid[r][c] = '.';
		}
		out.println(maxV);
		br.close();
		out.close();
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 56.875 / 70