Submission #1265251


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;
				}
			}
		}
		for (int depth = 1; depth <= K; depth++) {
			if (search(start_r, start_c, 0, dist_map, H, W, depth) == 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 2033 Byte
Status
Exec Time 2109 ms
Memory 34004 KB

Judge Result

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 246 ms 32324 KB
in10.txt 245 ms 30272 KB
in11.txt 220 ms 29580 KB
in12.txt 242 ms 32436 KB
in13.txt 215 ms 30248 KB
in14.txt 234 ms 30596 KB
in15.txt 235 ms 29640 KB
in16.txt 233 ms 32460 KB
in17.txt 264 ms 29768 KB
in18.txt 242 ms 30340 KB
in19.txt 237 ms 32784 KB
in2.txt 253 ms 30228 KB
in20.txt 120 ms 21972 KB
in21.txt 98 ms 20564 KB
in22.txt 97 ms 21844 KB
in23.txt 217 ms 32008 KB
in24.txt 229 ms 31180 KB
in25.txt 219 ms 30284 KB
in26.txt 2105 ms 30548 KB
in27.txt 229 ms 31852 KB
in28.txt 2108 ms 32740 KB
in29.txt 2108 ms 29776 KB
in3.txt 227 ms 30532 KB
in30.txt 2108 ms 34004 KB
in31.txt 227 ms 29580 KB
in32.txt 232 ms 32388 KB
in33.txt 2109 ms 30592 KB
in34.txt 2108 ms 30904 KB
in35.txt 385 ms 32868 KB
in36.txt 238 ms 30636 KB
in37.txt 233 ms 32524 KB
in38.txt 227 ms 32592 KB
in39.txt 234 ms 29912 KB
in4.txt 297 ms 29760 KB
in40.txt 233 ms 29952 KB
in5.txt 614 ms 31572 KB
in6.txt 240 ms 29652 KB
in7.txt 246 ms 32928 KB
in8.txt 236 ms 31712 KB
in9.txt 229 ms 32692 KB
sample1.txt 94 ms 21204 KB
sample2.txt 95 ms 19796 KB
sample3.txt 92 ms 18644 KB