Page 2 of 2
Re: 932 - Checking the N-Queens Problem
Posted: Thu Jun 26, 2008 8:44 am
by jurajz
dreadlord wrote:WARNING:
Don't try to solve this problem with a Pascal program. I believe there is some problem with the I/O in Pascal with the input file. I tried the following extremely simple program:
Code: Select all
program hang932;
var
TC, i, j : Integer;
car : Char;
begin
while eoln and not eof do readln; (* skip leading newlines *)
readln (TC);
i := 1;
repeat
j := 1;
repeat
car := '.';
repeat
if eoln then
readln
else
read (car)
until (car = '0') or (car = 'X');
if j = TC then break;
inc (j);
until False;
if i = TC then break;
inc (i);
until False;
writeln ('NO');
writeln ('NO')
end.
, which of course may not expect to get AC, but definitely shouldn't ever get Time Limit Exceeded, as it does. I get no problems when using this loops structure in my computer.
I believe this' something to do with the first readln(TC), as I get WA (as expected) when replacing the two outermost repeat-until loops by "for [ i | j ] := 1 to TC do". Maybe it gets zero for TC for some reason? Might this happen because the input text file contains some stranger line terminators, kind of DOS or so?
I coded it in Pascal and have no problem with reading the input. Here is reading part from my Pascal program:
Code: Select all
program pr932;
var tab:array[0..31,0..31]of char;
n,i,j:longint;
begin
while not eof(input) do
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do read(tab[i,j]);
readln;
end;
{ ... }
end;
end.
I have AC in 0.000.
Re: 932 - Checking the N-Queens Problem
Posted: Tue Apr 08, 2014 1:30 am
by brianfry713
This was a red check problem. I just created a dataset for it. There is no need for a special judge, I didn't include any cases in my input that have multiple correct outputs. The problem statement is now correct, there are multiple test cases.
Re: 932 - Checking the N-Queens Problem
Posted: Thu Jun 19, 2014 8:44 am
by lucastan
Hi all, I'm pretty sure I got this right but I keep getting WA.. any hint?
Code: Select all
#include<iostream>
#include<cstring>
using namespace std;
int row[100];
int col[100];
int d1[100];
int d2[100];
int board[35][35];
int n;
inline void set(int i, int j){row[i]=col[j]=d1[i+j]=d2[i-j+31]=1;}
inline void clear(int i, int j){row[i]=col[j]=d1[i+j]=d2[i-j+31]=0;}
inline int isset(int i, int j){return row[i] || col[j] || d1[i+j] || d2[i-j+31];}
int check(){
for (int i=0;i < n;i++)
for (int j=0;j < n;j++){
if(!board[i][j])continue;
if (isset(i,j))return 0;
set(i,j);
}
return 1;
}
int find(){
for (int a=1; a <= n;a++){
int found=1;
int arow, acol;
memset(row,0,sizeof row);
memset(col,0,sizeof col);
memset(d1,0,sizeof d1);
memset(d2,0,sizeof d2);
for (int i=0;i < n;i++){
for (int j=0;j < n;j++){
if (board[i][j]==a){arow=i;acol=j;}
if(board[i][j]==a ||!board[i][j])continue;
if (isset(i,j)){i=999;found=0;break;}
set(i,j);
}
}
if(found){
for (int i=0;i < n;i++)
for (int j=0;j < n;j++){
if(!isset(i,j)){
if(arow == i || acol == j || arow+acol == i+j || arow-acol==i-j){
board[arow][acol]=0;
board[i][j]=1;
return 1;
}
}
}
}
}
return 0;
}
int main(){
while(cin>>n){
memset(board, 0, sizeof board);
memset(row,0,sizeof row);
memset(col,0,sizeof col);
memset(d1,0,sizeof d1);
memset(d2,0,sizeof d2);
int f=1;
for (int i=0;i < n;i++)
for (int j=0;j < n;j++){
char c;
cin>>c;
if (c=='X'){
board[i][j]=f++;
}
}
if(check())cout<<"YES"<<endl;
else{
cout<<"NO"<<endl;
if(find()){
cout<<"YES"<<endl;
for (int i=0;i < n;i++){
for (int j=0;j < n;j++){
cout << (board[i][j] ? 'X':'0') ;
}
cout<<endl;
}
}else cout<<"NO"<<endl;
}
cout<<endl;
}
return 0;
}
Re: 932 - Checking the N-Queens Problem
Posted: Thu Jun 19, 2014 10:27 pm
by brianfry713
Print a blank line between test cases. Don't print an extra blank line at the end.