Submission #1304999

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

public class Hello
{

    public static void Main()
    {
        char[][] board = new char[8][];

        for(int i = 0; i < 8; i++)
        {
            board[i] = Console.ReadLine().ToCharArray();
        }

        if(DFS(0, 8, board))
        {
            for(int i = 0; i < 8; i++)
            {
                for(int j = 0; j < 8; j++)
                {
                    Console.Write(board[i][j]);
                }
                Console.WriteLine();
            }
        }
        else
        {
            Console.WriteLine("No Answer");
        }

        


        Console.ReadKey();
    }

    public static bool DFS(int current, int remains, char[][] board)
    {
        if (remains == 0) return true; // もし、８個全て置けたのであれば、true 
        if (current == 64) return false;  // もし、（上の式を満たすこと無く）全てのマスを探索したのであれば false

        // マス目の番号 current を座標に変換する。
        int y = current / 8;
        int x = current % 8;

        if(board[y][x] == 'Q') // 入力によって与えられたQの妥当性を検証する。
        {
            if(isPuttable(y, x, board)) // 与えられた位置のQが妥当であるか？
            {
                // 問題ないのであれば、そのまま探索を続ける。
                if (DFS(current + 1, remains - 1, board)) return true;
            }
        }
        else
        {
            // 現在の場所にQを置けるか？
            if(isPuttable(y, x, board))
            {
                // 置けるなら、Qを置き、そのまま探索を続ける。
                board[y][x] = 'Q';
                if (DFS(current + 1, remains - 1, board)) return true;
                board[y][x] = '.';
            }
            if (DFS(current + 1, remains, board)) return true;
        }
        return false;
    }

    public static bool isInside(int y, int x)
    {
        return x >= 0 && y >= 0 && x < 8 && y < 8;
    }

    public static bool isPuttable(int y, int x, char[][] board)
    {
        /*
         * 八方向全てを調べる。
         * vy が -1 vx が -1 時は、左斜めに vy が 0 vx が -1 の時は左へ
         * vy , vx が共に 0　の時は探索できないのでスキップする
         * vy が、0 vx が 1 の時は、右へ探索
         * というように、以下の処理で八方向全てを探索しきることができる。
         * 終了条件は、マス目をはみ出した時、すなわち、yが -1 or 8 x が -1 or 8の時
         */
        for (int vy = -1; vy <= 1; vy++)
        {
            for(int vx = -1; vx <= 1; vx++)
            {
                if (vy == 0 && vx == 0) continue;
                int ty = y; int tx = x;
                while(true)
                {
                    ty += vy; tx += vx;
                    if (!isInside(ty, tx)) break;
                    if (board[ty][tx] == 'Q') return false;
                }
            }
        }
        return true;
    }
}

Submission Info

Judge Result