Submission #1534842


Source Code Expand

#include <iostream>
#include <vector>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;

const int dx[] = {-1,0,1,-1,1,-1,0,1};
const int dy[] = {-1,-1,-1,0,0,1,1,1};
vector<string> board;

bool check(int y0, int x0)
{
  if(board[y0][x0] != '.')
    return false;

  rep(i,8) {
    for(int y=y0,x=x0; y>=0 && y<8 && x>=0 && x<8; y+=dy[i],x+=dx[i]) {
      if(y == y0 && x == x0)
        continue;
      if(board[y][x] == 'Q')
        return false;
    }
  }
  return true;
}


void next_yx(int *y, int *x)
{
  (*x)++;
  *y += *x/8;
  *x %= 8;
}


bool DFS(int y0, int x0, int n)
{
  if(n == 8)
    return true;
  if(y0 == 8)
    return false;

  int y = y0, x = x0;
  next_yx(&y, &x);

  if(DFS(y, x, n))
    return true;

  if(check(y0, x0)) {
    board[y0][x0] = 'Q';
    if(DFS(y, x, n+1))
      return true;
    board[y0][x0] = '.';
  }

  return false;
}


int main()
{
  board = vector<string>(8);
  rep(i,8) cin >> board[i];

  if(DFS(0, 0, 3)) {
    rep(i,8)
      cout << board[i] << endl;
  } else {
    cout << "No Answer" << endl;
  }

  return 0;
}

Submission Info

Submission Time
Task C - パズルのお手伝い
User osanamity
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1145 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