Submission #342763

#	Time	Username	Problem	Language	Result	Execution time	Memory
342763		dapig	Tracks in the Snow (BOI13_tracks)	Java	0 / 100	181 ms	12632 KiB

tracks

//package bfs;

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

class TracksSnow {

	public static void main(String[] args) throws IOException {

		TracksSnow obj = new TracksSnow();

		obj.doStuff();

	}

	private void doStuff() throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		char[][] grid = new char[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())];
		int[][] vis = new int[grid.length][grid[0].length];
		
		for (int i = 0; i < grid.length; i++) {
			grid[i] = br.readLine().toCharArray();
		}
		
		br.close();
		vis[0][0] = 1;

		ArrayDeque<int[]> q = new ArrayDeque<>();
		q.add(new int[] {0, 0});
		int[] yinc = new int[] {-1, 0, 1, 0};
		int[] xinc = new int[] {0, 1, 0, -1};
		int max = 1;
		while (!q.isEmpty()) {
			int[] next = q.poll();
			char thisChar = grid[next[0]][next[1]];
			int thisDist = vis[next[0]][next[1]];
			// first is y, second is x
			for (int i = 0; i < 4; i++) {
				int nexty = next[0]+yinc[i];
				int nextx = next[1]+xinc[i];
				if (nexty < 0 || nexty >= grid.length) continue;
				if (nextx < 0 || nextx >= grid[0].length) continue;
				if (vis[nexty][nextx] == 0 && grid[nexty][nextx] != '.') {
					if (grid[nexty][nextx] != thisChar) {
						vis[nexty][nextx] = thisDist+1;
						max = Math.max(max, thisDist+1);
						q.add(new int[] {nexty, nextx});
					} else {
						vis[nexty][nextx] = thisDist;
						q.push(new int[] {nexty, nextx});
					}
				}
			}
		}
		System.out.println(max);

	}

}

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