Bombs Chain [ AIZU ONLINE JUDGE 0071 ]

judge.u-aizu.ac.jp

問題

省略（リンク先参照）

考察

幅優先探索で解きます。
詳しい実装方法は以下のコードをご覧ください。

コード

void solve (FastScanner in, PrintWriter out, Methods ms) {

	int n = in.nextInt();
	
	for (int i=0; i<n; i++) {
		
		//平面を入力
		int[][] map = new int[8][8];
		for (int j=0; j<8; j++) {
			String s = in.next();
			for (int k=0; k<8; k++) {
				map[j][k] = s.charAt(k) - '0';
			}
		}
		
		//最初に爆発する爆弾の座標を登録
		ArrayDeque<Point> dq = new ArrayDeque<>();
		int x = in.nextInt()-1, y = in.nextInt()-1;
		dq.addLast(new Point(y, x));
		
		//幅優先探索
		while (dq.size() > 0) {
			
			//先頭の座標を一時変数に格納
			Point p = dq.removeFirst();
			
			//爆心地に0を代入
			map[p.y][p.x] = 0;
			
			//爆風を受ける座標（平面外を除いたもの）をリストとして取得する
			ArrayList<Point> temp = p.getAround(8, 8);
			
			//そのような座標のうち、爆弾が置かれている座標だけをキューに入れる
			for (int j=0; j<temp.size(); j++) {
				if (map[temp.get(j).y][temp.get(j).x] == 1) {
					dq.addLast(new Point(temp.get(j).y, temp.get(j).x));
				}
			}
			
		}
		
		//連鎖が終了した後の座標を出力する
		out.println("Data " + (i+1) + ":");
		printIntMap(out, map);
		
	}
	
}


static void printIntMap (PrintWriter out, int[][] map) {
	for (int i=0; i<map.length; i++) {
		for (int j=0; j<map[0].length; j++) {
			out.print(map[i][j]);
		}
		out.println();
	}
}


static class Point{
	
	int y, x;
	
	Point (int a, int b) {y=a; x=b;}
	
	int getY() {return y;}
	int getX() {return x;}
	
	ArrayList<Point> getAround (int limitY, int limitX) {
		ArrayList<Point> list = new ArrayList<>();
		list.add(new Point(y+1, x));
		list.add(new Point(y+2, x));
		list.add(new Point(y+3, x));
		list.add(new Point(y-1, x));
		list.add(new Point(y-2, x));
		list.add(new Point(y-3, x));
		list.add(new Point(y, x+1));
		list.add(new Point(y, x+2));
		list.add(new Point(y, x+3));
		list.add(new Point(y, x-1));
		list.add(new Point(y, x-2));
		list.add(new Point(y, x-3));
		for (int i=list.size()-1; i>=0; i--) {
			int y = list.get(i).y, x = list.get(i).x;
			if (x<0 || y<0 || x>=limitX || y>=limitY) {
				list.remove(i);
			}
		}
		return list;
	}
	
}