Submission #1265324


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;
				}
			}
		}
		if (search(start_r, start_c, 0, dist_map, H, W, K) == 0) {
			System.out.println(1);
			return;
		}
		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;
					}
				}
			}
		}
		System.out.println((min_dist - 1) / K + 2);
	}

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

Submission Info

Submission Time
Task C - Closed Rooms
User schwarzahl
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 1974 Byte
Status
Exec Time 2109 ms
Memory 34512 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 257 ms 30744 KB
in10.txt 236 ms 32632 KB
in11.txt 223 ms 30024 KB
in12.txt 229 ms 32876 KB
in13.txt 224 ms 29860 KB
in14.txt 234 ms 31568 KB
in15.txt 234 ms 33552 KB
in16.txt 227 ms 31952 KB
in17.txt 236 ms 30548 KB
in18.txt 222 ms 32452 KB
in19.txt 222 ms 31608 KB
in2.txt 230 ms 30148 KB
in20.txt 113 ms 23124 KB
in21.txt 104 ms 21844 KB
in22.txt 97 ms 19284 KB
in23.txt 228 ms 31340 KB
in24.txt 215 ms 29580 KB
in25.txt 226 ms 31956 KB
in26.txt 2109 ms 31832 KB
in27.txt 224 ms 29900 KB
in28.txt 2105 ms 31236 KB
in29.txt 221 ms 30544 KB
in3.txt 234 ms 31492 KB
in30.txt 2109 ms 31084 KB
in31.txt 218 ms 31160 KB
in32.txt 223 ms 33188 KB
in33.txt 224 ms 32592 KB
in34.txt 215 ms 32528 KB
in35.txt 376 ms 32364 KB
in36.txt 222 ms 31096 KB
in37.txt 229 ms 30292 KB
in38.txt 224 ms 34512 KB
in39.txt 221 ms 31988 KB
in4.txt 222 ms 31568 KB
in40.txt 212 ms 30676 KB
in5.txt 215 ms 31880 KB
in6.txt 231 ms 32460 KB
in7.txt 222 ms 32316 KB
in8.txt 217 ms 31108 KB
in9.txt 230 ms 32200 KB
sample1.txt 94 ms 21588 KB
sample2.txt 93 ms 21840 KB
sample3.txt 92 ms 21716 KB