Submission #1267991


Source Code Expand

Copy
/*http://agc014.contest.atcoder.jp/submissions/1266693*/
import java.util.ArrayDeque;
import java.util.Scanner;
import java.util.function.LongSupplier;
import java.util.stream.IntStream;
 
public class Main{
	static final Scanner s=new Scanner(System.in);
	static final long[] fal_rnd(long[] ar,LongSupplier sp){
		int l=-1,r=ar.length;
		while(l+1!=r)
			ar[Math.random()<0.5?++l:--r]=sp.getAsLong();
		return ar;
	}
	static final IntStream REPS(int v){
		return IntStream.range(0,v);
	};
	static int h,w,k;
	public static void main(String[] __){
		h=s.nextInt();
		w=s.nextInt();
		k=s.nextInt();
		char[][]f=new char[h][];
		int x=-1,y=-1;
		for(int i=0;i<h;i++) {
			String in=s.next();
			if(x==-1) {
				x=in.indexOf('S');
				y=i;
			}
			f[i]=in.toCharArray();
		}
		
		int u=y,d=y,r=x,l=x;
		
		int[]dx= {0,1,0,-1};
		int[]dy= {1,0,-1,0};
		
		
		ArrayDeque<Point> deque=new ArrayDeque<>();
		deque.add(new Point(y,x));
		for(int i=0;i<=k;i++) {
			for(int j=deque.size();j>0;j--) {
				Point poll=deque.poll();
				
				u=Math.min(u,poll.y);
				d=Math.max(d,poll.y);
				l=Math.min(l,poll.x);
				r=Math.max(r,poll.x);
				
				
				f[poll.y][poll.x]='#';
				for(int bufd=0;bufd<4;bufd++) {
					if(range(poll.y+dy[bufd],poll.x+dx[bufd])
							&&f[poll.y+dy[bufd]][poll.x+dx[bufd]]=='.') {
						deque.add(new Point(poll.y+dy[bufd],poll.x+dx[bufd]));
				f[poll.y+dy[bufd]][poll.x+dx[bufd]]='#';
					}
				}
			}
		}
		/*
		System.out.println(u);
		System.out.println(h-1-d);
		System.out.println(l);
		System.out.println(w-1-r);
		*/
		System.out.println((IntStream.of(u,h-1-d,l,w-1-r).min().getAsInt()+k-1)/k+1);
	}
	
	static final boolean range(int y,int x) {
		return 0<=y&&y<h&&0<=x&&x<w;
	}
	static class Point{
		int y,x;
		Point(int y,int x){
			this.y=y;
			this.x=x;
		}
	}
}

Submission Info

Submission Time
Task C - Closed Rooms
User eiya
Language Java8 (OpenJDK 1.8.0)
Score 700
Code Size 1879 Byte
Status
Exec Time 417 ms
Memory 43416 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 345 ms 30472 KB
in10.txt 290 ms 30796 KB
in11.txt 287 ms 29412 KB
in12.txt 271 ms 29092 KB
in13.txt 298 ms 29396 KB
in14.txt 294 ms 30088 KB
in15.txt 296 ms 29584 KB
in16.txt 262 ms 30704 KB
in17.txt 288 ms 29512 KB
in18.txt 288 ms 29132 KB
in19.txt 297 ms 29580 KB
in2.txt 288 ms 31216 KB
in20.txt 222 ms 25292 KB
in21.txt 177 ms 27092 KB
in22.txt 182 ms 24784 KB
in23.txt 297 ms 29680 KB
in24.txt 292 ms 30356 KB
in25.txt 294 ms 31632 KB
in26.txt 275 ms 29616 KB
in27.txt 285 ms 29124 KB
in28.txt 333 ms 33504 KB
in29.txt 356 ms 37752 KB
in3.txt 301 ms 29472 KB
in30.txt 309 ms 32780 KB
in31.txt 294 ms 28568 KB
in32.txt 286 ms 28768 KB
in33.txt 417 ms 42688 KB
in34.txt 409 ms 43416 KB
in35.txt 292 ms 31300 KB
in36.txt 295 ms 31100 KB
in37.txt 287 ms 29152 KB
in38.txt 291 ms 29528 KB
in39.txt 285 ms 30712 KB
in4.txt 301 ms 31288 KB
in40.txt 279 ms 33120 KB
in5.txt 296 ms 31400 KB
in6.txt 264 ms 28656 KB
in7.txt 295 ms 27856 KB
in8.txt 285 ms 31284 KB
in9.txt 279 ms 31736 KB
sample1.txt 167 ms 26708 KB
sample2.txt 172 ms 24784 KB
sample3.txt 172 ms 26832 KB