Submission #1370908
Source Code Expand
#include <iostream> #include <cstdlib> using namespace std; # define REP(i,n) for(int i=0; i<n;i++) bool ok(int n, bool board[8][8]){ int rows = n/8; int columns = n%8; REP(i,8){ REP(k,8){ if(board[i][k]==true){ if((i-rows)==0 || (k-columns)==0 || abs(i-rows)==abs(k-columns)){ return false; } } } } return true; } bool dfs(int n, int queens, bool board[8][8]){ //n:今どこのマスにいるか(0-63) //queens:残り置くべきクイーンの数(5-0) //board:今の盤面を表すbool配列[8][8] //nのマスに置くかどうかを試す // if(queens==0){ return true; } if(n==63){ // cout << "n=63 false" << endl; return false; } // cout << "dfs n=" << n << " queens=" << queens << endl; int r = n/8; int c = n%8; if (board[r][c]==true){ if(dfs(n+1, queens-1, board)) return true; }else{ if (ok(n,board)){ board[r][c] = true; // cout << "puts queen on " << n << endl; /* REP(i,8){ REP(k,8){ cout << board[i][k] << " "; } cout << endl; }*/ if(dfs(n+1, queens-1, board)) return true; board[r][c] = false; } if(dfs(n+1, queens, board)) return true; } // cout << "false (n=" << n << ")" << endl; return false; } int main(){ bool board[8][8]; string row; REP(i,8){ cin >> row; REP(k,8){ if(row[k]=='Q'){ board[i][k]=true; }else{ board[i][k]=false; } } } char b; if(dfs(0,8,board)){ REP(i,8){ REP(k,8){ if(board[i][k]){ b='Q'; }else{ b='.'; } cout << b; } cout << endl; } }else{ cout << "No Answer" << endl; } }
Submission Info
Submission Time | |
---|---|
Task | C - パズルのお手伝い |
User | sixty_deg |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1711 Byte |
Status | WA |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 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 | 1 ms | 256 KB |
00_sample2.txt | AC | 1 ms | 256 KB |
01_rnd_00.txt | AC | 1 ms | 256 KB |
01_rnd_01.txt | AC | 1 ms | 256 KB |
01_rnd_02.txt | WA | 1 ms | 256 KB |
01_rnd_03.txt | AC | 1 ms | 256 KB |
01_rnd_04.txt | WA | 1 ms | 256 KB |
01_rnd_05.txt | AC | 1 ms | 256 KB |
01_rnd_06.txt | WA | 1 ms | 256 KB |
01_rnd_07.txt | WA | 1 ms | 256 KB |
01_rnd_08.txt | WA | 1 ms | 256 KB |
01_rnd_09.txt | WA | 1 ms | 256 KB |
01_rnd_10.txt | AC | 1 ms | 256 KB |
01_rnd_11.txt | AC | 1 ms | 256 KB |
01_rnd_12.txt | AC | 1 ms | 256 KB |
01_rnd_13.txt | AC | 1 ms | 256 KB |
01_rnd_14.txt | WA | 1 ms | 256 KB |
01_rnd_15.txt | AC | 1 ms | 256 KB |
01_rnd_16.txt | AC | 1 ms | 256 KB |
01_rnd_17.txt | WA | 1 ms | 256 KB |
01_rnd_18.txt | AC | 1 ms | 256 KB |
01_rnd_19.txt | AC | 1 ms | 256 KB |
01_rnd_20.txt | AC | 1 ms | 256 KB |
01_rnd_21.txt | WA | 1 ms | 256 KB |
01_rnd_22.txt | WA | 1 ms | 256 KB |
01_rnd_23.txt | AC | 1 ms | 256 KB |
01_rnd_24.txt | WA | 1 ms | 256 KB |
01_rnd_25.txt | AC | 1 ms | 256 KB |
01_rnd_26.txt | WA | 1 ms | 256 KB |
01_rnd_27.txt | AC | 1 ms | 256 KB |
01_rnd_28.txt | AC | 1 ms | 256 KB |
01_rnd_29.txt | AC | 1 ms | 256 KB |
01_rnd_30.txt | AC | 1 ms | 256 KB |
01_rnd_31.txt | WA | 1 ms | 256 KB |
01_rnd_32.txt | AC | 1 ms | 256 KB |
01_rnd_33.txt | AC | 1 ms | 256 KB |
01_rnd_34.txt | WA | 1 ms | 256 KB |
01_rnd_35.txt | WA | 1 ms | 256 KB |
01_rnd_36.txt | AC | 1 ms | 256 KB |
01_rnd_37.txt | WA | 1 ms | 256 KB |
01_rnd_38.txt | AC | 1 ms | 256 KB |
01_rnd_39.txt | AC | 1 ms | 256 KB |