932 - Checking the N-Queens Problem

[jurajz]

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.

[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.

[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;
}

[brianfry713]

Print a blank line between test cases. Don't print an extra blank line at the end.