Submission #1264814


Source Code Expand

Copy
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Main main = new Main();
		main.solveC();
	}

	private void solveC() {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int K = sc.nextInt();
		sc.nextLine();
		int[][] dist_map = new int[H][];
		int start_r = -1;
		int start_c = -1;
		for (int r = 0; r < H; r++) {
			dist_map[r] = new int[W];
			String line = sc.nextLine();
			for (int c = 0; c < W; c++) {
				char panel = line.charAt(c);
				if (panel == 'S') {
					start_r = r;
					start_c = c;
					dist_map[r][c] = 1;
				} else if (panel == '#') {
					dist_map[r][c] = -1;
				} else {
					dist_map[r][c] = H * W * 2;
				}
			}
		}
		search(start_r, start_c, 0, dist_map, H, W);
		int min_dist = H + W;
		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				if (dist_map[r][c] <= K && dist_map[r][c] >= 0) {
					if (min_dist > r) {
						min_dist = r;
					}
					if (min_dist > c) {
						min_dist = c;
					}
					if (min_dist > H - 1 - r) {
						min_dist = H - 1 - r;
					}
					if (min_dist > W - 1 - c) {
						min_dist = W - 1 - c;
					}
				}
			}
		}
		if (min_dist == 0) {
			System.out.println(1);
		} else {
			System.out.println((min_dist - 1) / K + 2);
		}
	}

	private void search(int r, int c, int dist, int[][] map, int limit_r, int limit_c) {
		if (r < 0 || c < 0 || r >= limit_r || c >= limit_c) {
			return;
		}
		if (dist < map[r][c]) {
			map[r][c] = dist;
			search(r - 1, c, dist + 1, map, limit_r, limit_c);
			search(r, c - 1, dist + 1, map, limit_r, limit_c);
			search(r + 1, c, dist + 1, map, limit_r, limit_c);
			search(r, c + 1, dist + 1, map, limit_r, limit_c);
		}
	}
}

Submission Info

Submission Time
Task C - Closed Rooms
User schwarzahl
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 1783 Byte
Status
Exec Time 2108 ms
Memory 103380 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 0 / 700 sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
in1.txt 220 ms 30560 KB
in10.txt 224 ms 28848 KB
in11.txt 222 ms 30116 KB
in12.txt 234 ms 30708 KB
in13.txt 217 ms 30596 KB
in14.txt 235 ms 32280 KB
in15.txt 236 ms 31308 KB
in16.txt 233 ms 31316 KB
in17.txt 235 ms 30404 KB
in18.txt 219 ms 32180 KB
in19.txt 229 ms 32488 KB
in2.txt 234 ms 32488 KB
in20.txt 109 ms 20820 KB
in21.txt 97 ms 20564 KB
in22.txt 99 ms 21588 KB
in23.txt 227 ms 30360 KB
in24.txt 232 ms 30188 KB
in25.txt 222 ms 34176 KB
in26.txt 2105 ms 41972 KB
in27.txt 2105 ms 43596 KB
in28.txt 2105 ms 40992 KB
in29.txt 2105 ms 42244 KB
in3.txt 232 ms 30636 KB
in30.txt 2105 ms 35932 KB
in31.txt 2105 ms 43036 KB
in32.txt 2105 ms 41956 KB
in33.txt 2105 ms 87256 KB
in34.txt 2105 ms 103380 KB
in35.txt 2105 ms 93212 KB
in36.txt 220 ms 30004 KB
in37.txt 236 ms 30024 KB
in38.txt 226 ms 29220 KB
in39.txt 2108 ms 82884 KB
in4.txt 218 ms 29388 KB
in40.txt 2105 ms 75892 KB
in5.txt 212 ms 30668 KB
in6.txt 248 ms 29876 KB
in7.txt 215 ms 30668 KB
in8.txt 214 ms 30388 KB
in9.txt 246 ms 32588 KB
sample1.txt 94 ms 20820 KB
sample2.txt 96 ms 18900 KB
sample3.txt 98 ms 20564 KB