Submission #1265439


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 700
Code Size 1973 Byte
Status
Exec Time 264 ms
Memory 33176 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 700 / 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 240 ms 32948 KB
in10.txt 225 ms 31480 KB
in11.txt 217 ms 32068 KB
in12.txt 231 ms 30208 KB
in13.txt 223 ms 30796 KB
in14.txt 223 ms 31468 KB
in15.txt 224 ms 32372 KB
in16.txt 233 ms 30324 KB
in17.txt 245 ms 30668 KB
in18.txt 230 ms 32616 KB
in19.txt 216 ms 30252 KB
in2.txt 229 ms 30628 KB
in20.txt 119 ms 23124 KB
in21.txt 104 ms 19668 KB
in22.txt 96 ms 21332 KB
in23.txt 224 ms 31880 KB
in24.txt 234 ms 29584 KB
in25.txt 222 ms 32712 KB
in26.txt 241 ms 33176 KB
in27.txt 213 ms 29048 KB
in28.txt 242 ms 32828 KB
in29.txt 208 ms 30732 KB
in3.txt 235 ms 29448 KB
in30.txt 264 ms 32916 KB
in31.txt 218 ms 32364 KB
in32.txt 226 ms 30616 KB
in33.txt 231 ms 31796 KB
in34.txt 216 ms 30032 KB
in35.txt 234 ms 30604 KB
in36.txt 211 ms 32440 KB
in37.txt 235 ms 30800 KB
in38.txt 227 ms 29700 KB
in39.txt 233 ms 30524 KB
in4.txt 223 ms 29764 KB
in40.txt 211 ms 31924 KB
in5.txt 213 ms 31220 KB
in6.txt 225 ms 32100 KB
in7.txt 236 ms 30404 KB
in8.txt 222 ms 32720 KB
in9.txt 234 ms 28272 KB
sample1.txt 92 ms 21844 KB
sample2.txt 91 ms 18900 KB
sample3.txt 92 ms 19156 KB