oj.uz

Submission #582488

# Submission time Handle Problem Language Result Execution time Memory
582488 2022-06-23T23:02:47 Z coderInTraining Tracks in the Snow (BOI13_tracks) Java 11
0 / 100
 167 ms 12424 KB 
/*
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.0

# Verdict Execution time Memory Grader output
1 Runtime error 157 ms 11984 KB Execution failed because the return code was nonzero
2 Runtime error 136 ms 12112 KB Execution failed because the return code was nonzero
3 Runtime error 133 ms 12072 KB Execution failed because the return code was nonzero
4 Runtime error 141 ms 12092 KB Execution failed because the return code was nonzero
5 Runtime error 131 ms 12172 KB Execution failed because the return code was nonzero
6 Runtime error 167 ms 11956 KB Execution failed because the return code was nonzero
7 Runtime error 139 ms 12208 KB Execution failed because the return code was nonzero
8 Runtime error 137 ms 11952 KB Execution failed because the return code was nonzero
9 Runtime error 134 ms 11928 KB Execution failed because the return code was nonzero
10 Runtime error 149 ms 11972 KB Execution failed because the return code was nonzero
11 Runtime error 162 ms 11904 KB Execution failed because the return code was nonzero
12 Runtime error 128 ms 12112 KB Execution failed because the return code was nonzero
13 Runtime error 133 ms 12316 KB Execution failed because the return code was nonzero
14 Runtime error 131 ms 12312 KB Execution failed because the return code was nonzero
15 Runtime error 159 ms 12096 KB Execution failed because the return code was nonzero
16 Runtime error 139 ms 12000 KB Execution failed because the return code was nonzero
17 Runtime error 135 ms 11972 KB Execution failed because the return code was nonzero
18 Runtime error 130 ms 12064 KB Execution failed because the return code was nonzero

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 161 ms 12100 KB Execution failed because the return code was nonzero
2 Runtime error 144 ms 11956 KB Execution failed because the return code was nonzero
3 Runtime error 134 ms 12128 KB Execution failed because the return code was nonzero
4 Runtime error 137 ms 12368 KB Execution failed because the return code was nonzero
5 Runtime error 133 ms 12012 KB Execution failed because the return code was nonzero
6 Runtime error 149 ms 11792 KB Execution failed because the return code was nonzero
7 Runtime error 145 ms 11904 KB Execution failed because the return code was nonzero
8 Runtime error 133 ms 11996 KB Execution failed because the return code was nonzero
9 Runtime error 136 ms 12288 KB Execution failed because the return code was nonzero
10 Runtime error 148 ms 11912 KB Execution failed because the return code was nonzero
11 Runtime error 151 ms 12024 KB Execution failed because the return code was nonzero
12 Runtime error 133 ms 12092 KB Execution failed because the return code was nonzero
13 Runtime error 142 ms 12292 KB Execution failed because the return code was nonzero
14 Runtime error 147 ms 12044 KB Execution failed because the return code was nonzero
15 Runtime error 136 ms 12176 KB Execution failed because the return code was nonzero
16 Runtime error 139 ms 12256 KB Execution failed because the return code was nonzero
17 Runtime error 139 ms 11976 KB Execution failed because the return code was nonzero
18 Runtime error 146 ms 12000 KB Execution failed because the return code was nonzero
19 Runtime error 139 ms 12232 KB Execution failed because the return code was nonzero
20 Runtime error 137 ms 12064 KB Execution failed because the return code was nonzero
21 Runtime error 149 ms 11876 KB Execution failed because the return code was nonzero
22 Runtime error 141 ms 12112 KB Execution failed because the return code was nonzero
23 Runtime error 142 ms 12184 KB Execution failed because the return code was nonzero
24 Runtime error 142 ms 12240 KB Execution failed because the return code was nonzero
25 Runtime error 140 ms 11964 KB Execution failed because the return code was nonzero
26 Runtime error 158 ms 11884 KB Execution failed because the return code was nonzero
27 Runtime error 142 ms 11804 KB Execution failed because the return code was nonzero
28 Runtime error 142 ms 12092 KB Execution failed because the return code was nonzero
29 Runtime error 134 ms 12068 KB Execution failed because the return code was nonzero
30 Runtime error 131 ms 12424 KB Execution failed because the return code was nonzero
31 Runtime error 137 ms 12108 KB Execution failed because the return code was nonzero
32 Runtime error 161 ms 12136 KB Execution failed because the return code was nonzero