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 AC
Exec Time 417 ms
Memory 43416 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 46
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All 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 AC 345 ms 30472 KB
in10.txt AC 290 ms 30796 KB
in11.txt AC 287 ms 29412 KB
in12.txt AC 271 ms 29092 KB
in13.txt AC 298 ms 29396 KB
in14.txt AC 294 ms 30088 KB
in15.txt AC 296 ms 29584 KB
in16.txt AC 262 ms 30704 KB
in17.txt AC 288 ms 29512 KB
in18.txt AC 288 ms 29132 KB
in19.txt AC 297 ms 29580 KB
in2.txt AC 288 ms 31216 KB
in20.txt AC 222 ms 25292 KB
in21.txt AC 177 ms 27092 KB
in22.txt AC 182 ms 24784 KB
in23.txt AC 297 ms 29680 KB
in24.txt AC 292 ms 30356 KB
in25.txt AC 294 ms 31632 KB
in26.txt AC 275 ms 29616 KB
in27.txt AC 285 ms 29124 KB
in28.txt AC 333 ms 33504 KB
in29.txt AC 356 ms 37752 KB
in3.txt AC 301 ms 29472 KB
in30.txt AC 309 ms 32780 KB
in31.txt AC 294 ms 28568 KB
in32.txt AC 286 ms 28768 KB
in33.txt AC 417 ms 42688 KB
in34.txt AC 409 ms 43416 KB
in35.txt AC 292 ms 31300 KB
in36.txt AC 295 ms 31100 KB
in37.txt AC 287 ms 29152 KB
in38.txt AC 291 ms 29528 KB
in39.txt AC 285 ms 30712 KB
in4.txt AC 301 ms 31288 KB
in40.txt AC 279 ms 33120 KB
in5.txt AC 296 ms 31400 KB
in6.txt AC 264 ms 28656 KB
in7.txt AC 295 ms 27856 KB
in8.txt AC 285 ms 31284 KB
in9.txt AC 279 ms 31736 KB
sample1.txt AC 167 ms 26708 KB
sample2.txt AC 172 ms 24784 KB
sample3.txt AC 172 ms 26832 KB