Submission #666557

#	Time	Username	Problem	Language	Result	Execution time	Memory
666557		achejakhang	Tracks in the Snow (BOI13_tracks)	Java	82.50 / 100	2114 ms	473644 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());
		char[][] grid = new char[h][w];
		for (int i=0; i< h; i++) grid[i] = br.readLine().toCharArray();
		
		ArrayDeque<Integer> nextRow = new ArrayDeque<>();
		ArrayDeque<Integer> nextHeight = new ArrayDeque<>();
		ArrayDeque<Integer> nextValue = new ArrayDeque<>();
		nextRow.addLast(0);
		nextHeight.addLast(0);
		nextValue.addLast(1);
		int maxV = 1;
		while (!nextRow.isEmpty()) {
			int r = nextRow.removeFirst(), c = nextHeight.removeFirst(), v = nextValue.removeFirst();
			maxV = Math.max(maxV, v);
			if (r < h-1 && grid[r+1][c] != '.') {
				if (grid[r+1][c]==grid[r][c]) {
					nextRow.addFirst(r+1); nextHeight.addFirst(c); nextValue.addFirst(v);
				} else {
					nextRow.addLast(r+1); nextHeight.addLast(c); nextValue.addLast(v+1);
				}
			}
			if (r > 0 && grid[r-1][c] != '.') {
				if (grid[r-1][c]==grid[r][c]) {
					nextRow.addFirst(r-1); nextHeight.addFirst(c); nextValue.addFirst(v);
				} else {
					nextRow.addLast(r-1); nextHeight.addLast(c); nextValue.addLast(v+1);
				}
			}
			if (c < w-1 && grid[r][c+1] != '.') {
				if (grid[r][c+1]==grid[r][c]) {
					nextRow.addFirst(r); nextHeight.addFirst(c+1); nextValue.addFirst(v);
				} else {
					nextRow.addLast(r); nextHeight.addLast(c+1); nextValue.addLast(v+1);
				}
			}
			if (c > 0 && grid[r][c-1] != '.') {
				if (grid[r][c-1]==grid[r][c]) {
					nextRow.addFirst(r); nextHeight.addFirst(c-1); nextValue.addFirst(v);
				} else {
					nextRow.addLast(r); nextHeight.addLast(c-1); nextValue.addLast(v+1);
				}
			}
			grid[r][c] = '.';
		}
		out.println(maxV);
		br.close();
		out.close();
	}
}

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