Submission #582488

#	Time	Username	Problem	Language	Result	Execution time	Memory
582488		coderInTraining	Tracks in the Snow (BOI13_tracks)	Java	0 / 100	167 ms	12424 KiB

tracks

/*
import java.util.*;

public class tracksInTheSnowOJUZ {

    public static int [] dR = {-1, 0, 1, 0};
    public static int [] dC = {0, 1, 0, -1};
    public static void main (String[]args) {
        Scanner scan = new Scanner (System.in);

        int rows = scan.nextInt();
        int columns = scan.nextInt();

        char [][] grid = new char [rows][columns];

        for (int i = 0; i < rows; i++) {
            String line = scan.next();

            for (int j = 0; j < columns; j++) {
                grid[i][j] = line.charAt(j);
            }
        }

        int [][] distances = new int [rows][columns];

        for (int i = 0; i < rows; i++)  {
            Arrays.fill(distances[i], Integer.MAX_VALUE);
        }

        distances[0][0] = 1;

        Queue <Pair> queue = new LinkedList <Pair>();
        Pair startingPair = new Pair (0, 0);
        queue.add(startingPair);

        int maxDist = 0;

        while (queue.isEmpty() == false) {
            Pair curPair = queue.poll();
            int cRow = curPair.row;
            int cColumn = curPair.column;
            int curDist = distances[cRow][cColumn];

            maxDist = Math.max(maxDist, curDist);

            char curChar = grid[cRow][cColumn];

            for (int i = 0; i < 4; i++) {
                int nextRow = cRow + dR[i];
                int nextColumn = cColumn + dC[i];

                if (nextRow >= rows || nextColumn >= columns || nextRow < 0 || nextColumn < 0) {
                    continue;
                }

                if (grid[nextRow][nextColumn] == '.') {
                    continue;
                }

                if (grid[nextRow][nextColumn] == curChar) {
                    if (curDist < distances[nextRow][nextColumn]) {
                        distances[nextRow][nextColumn] = curDist;
                        Pair addingPair = new Pair (nextRow, nextColumn);
                        queue.add(addingPair);
                    }
                }
                else {
                    if (curDist + 1 < distances[nextRow][nextColumn]) {
                        distances[nextRow][nextColumn] = curDist + 1;
                        Pair addingPair = new Pair (nextRow, nextColumn);
                        queue.add(addingPair);
                    }
                }
            }
        }

        System.out.println(maxDist);
    }

    private static class Pair {
        int row;
        int column;

        public Pair (int row, int column) {
            this.row = row;
            this.column = column;
        }
    }
}
*/

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

class Main {
	static final int[] dx = {0, 0, -1, 1};
	static final int[] dy = {-1, 1, 0, 0};
	static int N = 1, H, W;
	static int[][] grid, count;
	public static void main(String[] args) {
		FastIO io = new FastIO();

		H = io.nextInt();
		W = io.nextInt();
		grid = new int[H][W];

		for (int i = 0; i < H; i++) {
			String line = io.next();
			for (int j = 0; j < W; j++) {
				grid[i][j] = (line.charAt(j) == 'F')?1:(line.charAt(j) == 'R')?2:-1;
			}
		}

		io.println(bfs());
		io.close();
	}

	private static int bfs() {
		count = new int[H][W];

		LinkedList<int[]> q = new LinkedList<>();
		q.add(new int[]{0,0});
		count[0][0] = 1;

		while (!q.isEmpty()) {
			int[] curr = q.poll();

			N = Math.max(N, count[curr[0]][curr[1]]);

			for (int i = 0; i < 4; i++) {
				int nx = curr[0] + dx[i];
				int ny = curr[1] + dy[i];

				if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
				if(count[nx][ny] > 0) continue;
				if(grid[nx][ny] == -1) continue;
				if(grid[nx][ny] != grid[curr[0]][curr[1]]) {
					count[nx][ny] = count[curr[0]][curr[1]] + 1;
					q.addLast(new int[]{nx, ny});
				}
				else {
					count[nx][ny] = count[curr[0]][curr[1]];
					q.addFirst(new int[]{nx, ny});
				}
			}
		}

		return N;
	}

	private static class FastIO extends PrintWriter {
		private InputStream stream;
		private byte[] buf = new byte[1<<16];
		private int curChar, numChars;

		// standard input
		public FastIO() { this(System.in,System.out); }
		public FastIO(InputStream i, OutputStream o) {
			super(o);
			stream = i;
		}
		// file input
		public FastIO(String i, String o) throws IOException {
			super(new FileWriter(o));
			stream = new FileInputStream(i);
		}

		// throws InputMismatchException() if previously detected end of file
		private int nextByte() {
			if (numChars == -1) throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars == -1) return -1; // end of file
			}
			return buf[curChar++];
		}

		// to read in entire lines, replace c <= ' '
		// with a function that checks whether c is a line break
		public String next() {
			int c; do { c = nextByte(); } while (c <= ' ');
			StringBuilder res = new StringBuilder();
			do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
			return res.toString();
		}
		public int nextInt() { // nextLong() would be implemented similarly
			int c; do { c = nextByte(); } while (c <= ' ');
			int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = 10*res+c-'0';
				c = nextByte();
			} while (c > ' ');
			return res * sgn;
		}
		public double nextDouble() { return Double.parseDouble(next()); }
	}
}

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