Submission #548532

#	Time	Username	Problem	Language	Result	Execution time	Memory
548532		Benqt	Tracks in the Snow (BOI13_tracks)	Java	95.63 / 100	2112 ms	544124 KiB

tracks

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

public class tracks {
	static int h;
	static int w;
	static char[][] arr;
	static int[][] dist;
	public static void main(String[] args) {
		Kattio io = new Kattio();
		h = io.nextInt();
		w = io.nextInt();
		arr = new char[h][w];
		dist = new int[h][w];
		for (int i=0; i<h; i++) {
			String s = io.next();
			for (int j=0; j<w; j++) {
				arr[i][j] = s.charAt(j);
			}
		}

		dist[0][0] = 1;
		Deque<int[]> q = new LinkedList<>();
		q.add(new int[]{0, 0});
		while (!q.isEmpty()) {
			int[] curr = q.poll();
			int x = curr[0];
			int y = curr[1];
			for (int i=0; i<4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx >= h || ny < 0 || ny >= w
					|| dist[nx][ny] > 0
					|| arr[nx][ny] == '.') {
					continue;
				}

				if (arr[x][y] != arr[nx][ny]) {
					dist[nx][ny] = dist[x][y] + 1;
					q.addLast(new int[]{nx, ny});
				} else {
					dist[nx][ny] = dist[x][y];
					q.addFirst(new int[]{nx, ny});
				}
			}
		}
		int max = 0;
		for (int i=0; i<h; i++) {
			for (int j=0; j<w; j++) {
				//System.out.print(dist[i][j] + " ");
				max = Math.max(max, dist[i][j]);
			}
			//System.out.println();
		}
		System.out.println(max);
	}

	static final int[] dx = {1, -1, 0, 0};
	static final int[] dy = {0, 0, 1, -1};

	static class Kattio extends PrintWriter {
		private BufferedReader r;
		private StringTokenizer st;

		// standard input
		public Kattio() { this(System.in, System.out); }
		public Kattio(InputStream i, OutputStream o) {
			super(o);
			r = new BufferedReader(new InputStreamReader(i));
		}
		// USACO-style file input
		public Kattio(String problemName) throws IOException {
			super(new FileWriter(problemName + ".out"));
			r = new BufferedReader(new FileReader(problemName + ".in"));
		}

		// returns null if no more input
		public String next() {
			try {
				while (st == null || !st.hasMoreTokens())
					st = new StringTokenizer(r.readLine());
				return st.nextToken();
			} catch (Exception e) { }
			return null;
		}

		public int nextInt() { return Integer.parseInt(next()); }
		public double nextDouble() { return Double.parseDouble(next()); }
		public long nextLong() { return Long.parseLong(next()); }
	}
}

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