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
Submission Time | |
---|---|
Task | C - パズルのお手伝い |
User | chokudai |
Language | Java (OpenJDK 1.7.0) |
Score | 100 |
Code Size | 2155 Byte |
Status | AC |
Exec Time | 623 ms |
Memory | 23272 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample1.txt, 00_sample2.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 01_rnd_21.txt, 01_rnd_22.txt, 01_rnd_23.txt, 01_rnd_24.txt, 01_rnd_25.txt, 01_rnd_26.txt, 01_rnd_27.txt, 01_rnd_28.txt, 01_rnd_29.txt, 01_rnd_30.txt, 01_rnd_31.txt, 01_rnd_32.txt, 01_rnd_33.txt, 01_rnd_34.txt, 01_rnd_35.txt, 01_rnd_36.txt, 01_rnd_37.txt, 01_rnd_38.txt, 01_rnd_39.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample1.txt | AC | 623 ms | 23116 KB |
00_sample2.txt | AC | 483 ms | 23136 KB |
01_rnd_00.txt | AC | 489 ms | 23160 KB |
01_rnd_01.txt | AC | 494 ms | 23136 KB |
01_rnd_02.txt | AC | 465 ms | 23100 KB |
01_rnd_03.txt | AC | 466 ms | 23272 KB |
01_rnd_04.txt | AC | 462 ms | 23132 KB |
01_rnd_05.txt | AC | 495 ms | 23264 KB |
01_rnd_06.txt | AC | 488 ms | 23132 KB |
01_rnd_07.txt | AC | 486 ms | 23132 KB |
01_rnd_08.txt | AC | 457 ms | 23132 KB |
01_rnd_09.txt | AC | 474 ms | 23132 KB |
01_rnd_10.txt | AC | 482 ms | 23128 KB |
01_rnd_11.txt | AC | 482 ms | 23216 KB |
01_rnd_12.txt | AC | 500 ms | 23000 KB |
01_rnd_13.txt | AC | 506 ms | 23136 KB |
01_rnd_14.txt | AC | 503 ms | 23012 KB |
01_rnd_15.txt | AC | 484 ms | 23140 KB |
01_rnd_16.txt | AC | 496 ms | 23132 KB |
01_rnd_17.txt | AC | 502 ms | 23128 KB |
01_rnd_18.txt | AC | 497 ms | 23004 KB |
01_rnd_19.txt | AC | 498 ms | 23136 KB |
01_rnd_20.txt | AC | 508 ms | 23196 KB |
01_rnd_21.txt | AC | 494 ms | 23016 KB |
01_rnd_22.txt | AC | 506 ms | 23100 KB |
01_rnd_23.txt | AC | 526 ms | 23132 KB |
01_rnd_24.txt | AC | 518 ms | 23004 KB |
01_rnd_25.txt | AC | 513 ms | 23176 KB |
01_rnd_26.txt | AC | 495 ms | 23140 KB |
01_rnd_27.txt | AC | 510 ms | 23136 KB |
01_rnd_28.txt | AC | 497 ms | 23260 KB |
01_rnd_29.txt | AC | 510 ms | 23136 KB |
01_rnd_30.txt | AC | 520 ms | 23128 KB |
01_rnd_31.txt | AC | 517 ms | 23132 KB |
01_rnd_32.txt | AC | 478 ms | 23136 KB |
01_rnd_33.txt | AC | 497 ms | 23144 KB |
01_rnd_34.txt | AC | 506 ms | 23132 KB |
01_rnd_35.txt | AC | 492 ms | 23140 KB |
01_rnd_36.txt | AC | 483 ms | 23124 KB |
01_rnd_37.txt | AC | 521 ms | 23132 KB |
01_rnd_38.txt | AC | 523 ms | 23260 KB |
01_rnd_39.txt | AC | 508 ms | 23216 KB |