Submission #582487

#	Time	Username	Problem	Language	Result	Execution time	Memory
582487		coderInTraining	Tracks in the Snow (BOI13_tracks)	Java	0 / 100	149 ms	12356 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) {
		Scanner scan = new Scanner (System.in);

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

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

		System.out.println(bfs());
	}

	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;
	}
}

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