Submission #10927153

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

char board[8][8];

bool inBoard(int ty,int tx)
{
        if( 0<=ty&&ty<=7 && 0<=tx&&tx<=7 )return true;
        return false;
}

bool isOK(int y,int x)
{
        int ty,tx;
        for(int dy=-1;dy<=1;dy++)
        {
                for(int dx=-1;dx<=1;dx++)
                {
                        if(dy==0&&dx==0)continue;
                        ty=y; tx=x;
                        while(true)
                        {
                                ty+=dy; tx+=dx;
                                if(inBoard(ty,tx)==false)break;
                                if(board[ty][tx]=='Q')return false;
                        }
                }
        }
        return true;
}

bool dfs(int pos,int nokori)
{
        if(nokori==0)return true;
        if(pos==64)return false;

        int y=pos/8;
        int x=pos%8;

        if(board[y][x]=='Q')
        {
                if(isOK(y,x))
                {
                        if(dfs(pos+1,nokori-1))return true;
                }else
                {
                        return false;
                }
        }else
        {
                if(isOK(y,x))
                {
                        board[y][x]='Q';
                        if(dfs(pos+1,nokori-1))return true;
                        else board[y][x]='.';
                }
                if(dfs(pos+1,nokori))return true;
        }
        return false;
}


main()
{
        for(int i=0;i<8;i++)
        {
                for(int j=0;j<8;j++)
                {
                        cin>>board[i][j];
                }
        }

        if(dfs(0,8))
        {
                for(int i=0;i<8;i++)
                {
                        for(int j=0;j<8;j++)
                        {
                                cout<<board[i][j];
                        }
                        cout<<endl;
                }
        }else
        {
                cout<<"No Answer"<<endl;
        }
}

Submission Info

Judge Result