Submission #1265038


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, K);
		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, int K) {
		if (dist > K || 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, K);
			search(r, c - 1, dist + 1, map, limit_r, limit_c, K);
			search(r + 1, c, dist + 1, map, limit_r, limit_c, K);
			search(r, c + 1, dist + 1, map, limit_r, limit_c, K);
		}
	}
}

Submission Info

Submission Time
Task C - Closed Rooms
User schwarzahl
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 1819 Byte
Status
Exec Time 2105 ms
Memory 110664 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 224 ms 30260 KB
in10.txt 222 ms 30452 KB
in11.txt 222 ms 34248 KB
in12.txt 228 ms 30152 KB
in13.txt 221 ms 31136 KB
in14.txt 226 ms 31888 KB
in15.txt 234 ms 29584 KB
in16.txt 235 ms 29580 KB
in17.txt 218 ms 29524 KB
in18.txt 228 ms 30260 KB
in19.txt 220 ms 31424 KB
in2.txt 214 ms 29620 KB
in20.txt 110 ms 23892 KB
in21.txt 98 ms 21076 KB
in22.txt 106 ms 20564 KB
in23.txt 219 ms 32320 KB
in24.txt 223 ms 33428 KB
in25.txt 225 ms 32724 KB
in26.txt 248 ms 32128 KB
in27.txt 223 ms 29388 KB
in28.txt 430 ms 32312 KB
in29.txt 1215 ms 32112 KB
in3.txt 231 ms 29664 KB
in30.txt 271 ms 31928 KB
in31.txt 221 ms 31884 KB
in32.txt 218 ms 32176 KB
in33.txt 2105 ms 110664 KB
in34.txt 2105 ms 45032 KB
in35.txt 231 ms 31816 KB
in36.txt 220 ms 31692 KB
in37.txt 217 ms 31948 KB
in38.txt 223 ms 30512 KB
in39.txt 226 ms 30868 KB
in4.txt 225 ms 32084 KB
in40.txt 219 ms 29520 KB
in5.txt 222 ms 31924 KB
in6.txt 238 ms 29312 KB
in7.txt 228 ms 30668 KB
in8.txt 238 ms 32740 KB
in9.txt 233 ms 32868 KB
sample1.txt 93 ms 19668 KB
sample2.txt 102 ms 21204 KB
sample3.txt 92 ms 19540 KB