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
AC × 26
WA × 16
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