Submission #145104

---

Source Code Expand

import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		new Main().run();
	}



	void run()
	{
		Scanner cin = new Scanner(System.in);

		//入力を受け取り、char型の配列に写す
		char[][] board = new char[8][8];
		for(int i=0;i<8;i++){
			String st = cin.next();
			for(int j=0;j<8;j++){
				board[i][j] = st.charAt(j);
			}
		}

		//もし条件を満たす解があれば出力
		if(dfs(0, 8, board)){
			for(int i=0;i<8;i++){
				for(int j=0;j<8;j++){
					System.out.print(board[i][j]);
				}
				System.out.println();
			}
		}
		//なければNo Answerを出力
		else System.out.println("No Answer");
	}


	boolean dfs(int pos, int nokori, char[][] board)
	{
		//もし8個の駒が置けたなら、trueを返す。
		if(nokori==0) return true;

		//もしもう置く場所がないなら、falseを返す。
		if(pos==64) return false;

		//整数posを座標に変換
		int y = pos / 8;
		int x = pos % 8;

		//もし絶対に置かないといけない場所なら
		if(board[y][x] == 'Q'){
			//駒を置いても大丈夫なのであれば、置いて探索を続ける
			if(isPuttable(y, x, board))
				if(dfs(pos+1, nokori-1, board)) return true;
		}
		//違えば、両方試す。
		else{
			//置ける場所なのであれば、置いてから探索を続ける。
			if(isPuttable(y, x, board)){
				board[y][x] = 'Q';
				if(dfs(pos+1, nokori-1, board)) return true;
				board[y][x] = '.';
			}

			if(dfs(pos+1, nokori, board)) return true;
		}
		return false;
	}

	boolean ok(int y, int x){
		return y >= 0 && x >= 0 && y < 8 && x < 8;
	}

	boolean isPuttable(int y, int x, char[][] board){
		//8方向全部調べる
		for(int vy=-1; vy<=1; vy++){
			for(int vx=-1; vx<=1; vx++){
				if(vy==0 && vx==0) continue;
				//はみ出るまで移動して、駒を見つけたらfalse
				int ty=y, tx=x;
				while(true){
					ty += vy; tx += vx;
					if(!ok(ty,tx)) break;
					if(board[ty][tx] == 'Q') return false;
				}
			}
		}
		//何も重複がなければtrueを返す
		return true;
	}
}

Submission Info

Judge Result