質問する

昌栄と尚勤は洞窟で所有権を主張した.二人は棒を相手に投げる方法で誰に属するかを決める.戦いは洞窟で繰り広げられる.洞窟には鉱物が貯蔵されており、投げた棒は鉱物を破壊する可能性がある.
洞窟はR行C列、R列として表示できます.×C格子からなる.各格子は空またはミネラルを含み、隣接する2つの4つの方向の1つのミネラルを含む格子は同じ群である.
昌永は洞窟の左側に立っていて、上根は右側に立っています.二人は交代で棒を投げた.棒を投げる前に投げる高さを決めます.棒が地面と平らに飛ぶ.
木の棒が鉱物にぶつかると、格子の中の鉱物が破壊され、木の棒はその場で移動を停止します.
鉱物が破壊されると、残りのクラスタが分離される可能性があります.新しく生成されたクラスタが浮遊すると、重力は底部まで下がります.降下の間、クラスタの形状は変化しません.クラスタは、別のクラスタまたは土地に遭遇する前に、クラスタから分離される.クラスタ内で他のクラスタにドロップし、マージできます.
洞窟の中の鉱物の形と二人で投げた棒の高さ.すべての棒を投げ終わったら、鉱物の形を得るプログラムを書いてください.

入力

第1列は、穴の大きさRおよびCを与える.(1 ≤ R,C ≤ 100)
次のR行にはC文字,"."スペース、xは鉱物を表します.
次の行は棒を投げる回数Nを与える.(1 ≤ N ≤ 100)
最後の行にはレバーの高さがあり、スペースで区切られています.すべての高さは1とRの間にあり、高さ1は行列の最下部を表し、Rは最上位を表す.1本目の棒は左から右に投げ、2本目は右から左に投げ、このように順番に投げます.
空中に浮かぶ鉱物の群れもなく、2つ以上の群れが同時に落下することもない.

しゅつりょく

鉱物形状を入力形式と同じ形式で出力します.

I/O例

に答える

高さと方向の鉱物除去

の下部にあるクラスタ

へのアクセス

2アクセスされていないクラスタ

を下に移動

すべてのラウンドが終わる前に、1から3つのプロセス

を繰り返します.

コード#コード#

import java.io.*;
import java.util.*;

public class Main_B18500 {
	static char[][]map;
	static int R,C;
	static boolean[][] vistied;
	static int[]dx= {1,-1,0,0};
	static int[]dy= {0,0,1,-1};
	static Queue<int[]>cluster=new LinkedList<>();;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st=new StringTokenizer(br.readLine());
		StringBuilder sb=new StringBuilder();
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		
		map=new char[R][C];
		for(int i=0;i<R;i++)map[i]=br.readLine().toCharArray();
		
		int cnt=Integer.parseInt(br.readLine());
		st=new StringTokenizer(br.readLine());
		
		for(int t=0;t<cnt;t++){
			int height=R-Integer.parseInt(st.nextToken());
			remove(t%2,height);
			vistied=new boolean[R][C];
			//바닥에 있는 미네랄 모두 방문 체크
			for(int i=0;i<C;i++) {
				if(map[R-1][i]=='x'&&!vistied[R-1][i])
					bfs(R-1,i);
			}
			boolean downCheck=false;
			//공중에 있는 클러스터를 찾아 아래로
			//문제에서 1개이하의 클러스터만 떨어진다고 했으므로 하나가 떨어지면 반복문 종료 
			for(int i=0;i<R;i++) {
				if(downCheck)break;
				for(int j=0;j<C;j++) {
					if(map[i][j]=='x'&&!vistied[i][j]) {
						bfs(i,j);
						down();
						downCheck=true;
						break;
					}
				}
			}
		}
		for(char[]a:map) {
			for(char c:a) {
				sb.append(c);
			}
			sb.append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
	}
	//높이와 방향에 따라 미네랄 파괴
	static void remove(int d,int height) {
		int i=0;
		if(d==0) {
			for(i=0;i<C;i++) {
				if(map[height][i]=='x') {
					map[height][i]='.';
					break;
				}
			}
		}
		else {
			for(i=C-1;i>=0;i--) {
				if(map[height][i]=='x') {
					map[height][i]='.';
					break;
				}
			}
		}
	}
	//클러스터 찾기
	static void bfs(int x,int y) {
		Queue<int[]>q=new LinkedList<>();
		cluster.clear();
		cluster.add(new int[] {x,y});
		q.add(new int[] {x,y});
		vistied[x][y]=true;
		while(!q.isEmpty()) {
			int[]temp=q.poll();
			for(int i=0;i<4;i++) {
				int nx=temp[0]+dx[i];
				int ny=temp[1]+dy[i];
				if(nx>=0&&ny>=0&&nx<R&&ny<C&&!vistied[nx][ny]&&map[nx][ny]=='x') {
					vistied[nx][ny]=true;
					cluster.add(new int[] {nx,ny});
					q.add(new int[] {nx,ny});
				}
			}
		}
	}
	//분리되어 있는 클러스터를 아래로 이동
	static void down() {
		int[][]temp=new int[cluster.size()][2];
		int i=0,minus=0,size=temp.length;
		while(!cluster.isEmpty()) {
			temp[i++]=cluster.poll();
		}
		change(0, size, temp, '.');
		while(true) {
			if(check(minus+1, size, temp))minus++;
			else break;
		}
		change(minus, size, temp, 'x');
	}
	//map 상태 변경
	static void change(int minus,int size,int[][] temp,char c) {
		for(int i=0;i<size;i++) {
			int nx = temp[i][0]+minus;
			int ny = temp[i][1];
			map[nx][ny]=c;
		}
	}
	//내려갈 수 있는지 확인
	static boolean check(int minus,int size,int[][] temp) {
		for(int i=0;i<size;i++) {
			int nx = temp[i][0]+minus;
			int ny = temp[i][1];
			if(nx>=R||map[nx][ny]=='x') return false;
		}
		return true;
	}
}