Submission #1611547


Source Code Expand

fn main() {
  let board_init: Vec<(i32, i32)> = read_board();
  
  if !valid_arrangement(&board_init) {
    println!("No Answer");
    return;
  }
  
  let x_placed_init = board_init.iter().map(|p|p.0).collect::<Vec<_>>();
  let y_placed_init = board_init.iter().map(|p|p.1).collect::<Vec<_>>();
  
  let x_cand = (1..9).filter(|i| !x_placed_init.contains(i)).collect::<Vec<_>>();
  let y_cand = (1..9).filter(|j| !y_placed_init.contains(j)).collect::<Vec<_>>();
  
  let mut cand: Vec<(i32, i32)> = vec![];
  for i in x_cand {
    for j in y_cand.clone() {
      cand.push((i,j));
    }
  }
  
  let mut board = board_init.clone();
  for mut comb in combination(&cand, 5).iter_mut() {
    board = board_init.clone();
    board.append(&mut comb);
    if valid_arrangement(&board) {
      break;
    }
  }
  
  print_board(&board);
}

fn combination<T: Clone>(vec: &Vec<T>, r: usize) -> Vec<Vec<T>> {
  let l = vec.len();
  let mut acc: Vec<Vec<T>> = vec![];

  fn go<T: Clone>(vec: &Vec<T>, l: usize, r: usize, i: usize, buf: &mut Vec<T>, acc: &mut Vec<Vec<T>>) {
    if r == 0 {
      acc.push(buf.clone());
    } else if i < l {
      buf.push(vec[i].clone());
      go(vec, l, r-1, i+1, buf, acc);
      buf.pop();
      go(vec, l, r, i+1, buf, acc);
    }
  }

  go (vec, l, r, 0, &mut vec![], &mut acc);
  acc
}

fn valid_arrangement(board: &Vec<(i32, i32)>) -> bool {
  fn valid(((x1,y1),(x2,y2)): ((i32,i32),(i32,i32))) -> bool {
    x1 != x2 && y1 != y2 && (x2-x1).abs() != (y2-y1).abs()
  }

  let mut buf: Vec<((i32,i32),(i32,i32))> = vec![];
  for (i, &p1) in board.iter().enumerate() {
    for (j, &p2) in board.iter().enumerate() {
      if i < j {
        buf.push((p1,p2));
      }
    }
  }
  
  buf.into_iter().all(valid)
}

fn read_board() -> Vec<(i32, i32)> {
  let lines: Vec<String> = reads(8);
  
  let mut buf: Vec<(i32, i32)> = vec![];
  for (line, i) in lines.iter().zip(1..) {
    for (c, j) in line.chars().zip(1..) {
      if c == 'Q' {
        buf.push((i as i32, j as i32));
      }
    }
  }
  buf
}

fn print_board(board: &Vec<(i32, i32)>) {
  for i in 1 .. 9 {
    for j in 1 .. 9 {
      print!("{}", if board.contains(&(i,j)) {"Q"} else {"."});
    }
    println!("");
  }
  println!("");
}

fn reads<T: std::str::FromStr>(n: usize) -> Vec<T> {
  let mut vec: Vec<T> = vec![];
  for _ in 0 .. n {
    vec.push(read());
  }
  vec
}

fn read<T: std::str::FromStr>() -> T {
  let mut buf = String::new();
  std::io::stdin().read_line(&mut buf).ok();
  buf.trim().parse::<T>().ok().unwrap()
}

Submission Info

Submission Time
Task C - パズルのお手伝い
User aimy
Language Rust (1.15.1)
Score 0
Code Size 2628 Byte
Status WA
Exec Time 23 ms
Memory 8444 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 35
WA × 7
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 9 ms 8444 KB
00_sample2.txt AC 2 ms 4352 KB
01_rnd_00.txt WA 23 ms 8444 KB
01_rnd_01.txt AC 9 ms 8444 KB
01_rnd_02.txt AC 2 ms 4352 KB
01_rnd_03.txt WA 23 ms 8444 KB
01_rnd_04.txt AC 2 ms 4352 KB
01_rnd_05.txt WA 23 ms 8444 KB
01_rnd_06.txt AC 2 ms 4352 KB
01_rnd_07.txt AC 2 ms 4352 KB
01_rnd_08.txt AC 2 ms 4352 KB
01_rnd_09.txt AC 2 ms 4352 KB
01_rnd_10.txt AC 2 ms 4352 KB
01_rnd_11.txt AC 2 ms 4352 KB
01_rnd_12.txt AC 2 ms 4352 KB
01_rnd_13.txt AC 16 ms 8444 KB
01_rnd_14.txt AC 2 ms 4352 KB
01_rnd_15.txt AC 2 ms 4352 KB
01_rnd_16.txt AC 2 ms 4352 KB
01_rnd_17.txt AC 2 ms 4352 KB
01_rnd_18.txt AC 13 ms 8444 KB
01_rnd_19.txt AC 12 ms 8444 KB
01_rnd_20.txt AC 2 ms 4352 KB
01_rnd_21.txt AC 2 ms 4352 KB
01_rnd_22.txt AC 2 ms 4352 KB
01_rnd_23.txt WA 23 ms 8444 KB
01_rnd_24.txt AC 2 ms 4352 KB
01_rnd_25.txt AC 16 ms 8444 KB
01_rnd_26.txt AC 2 ms 4352 KB
01_rnd_27.txt AC 9 ms 8444 KB
01_rnd_28.txt WA 23 ms 8444 KB
01_rnd_29.txt AC 2 ms 4352 KB
01_rnd_30.txt AC 2 ms 4352 KB
01_rnd_31.txt AC 2 ms 4352 KB
01_rnd_32.txt AC 12 ms 8444 KB
01_rnd_33.txt AC 2 ms 4352 KB
01_rnd_34.txt AC 2 ms 4352 KB
01_rnd_35.txt AC 2 ms 4352 KB
01_rnd_36.txt AC 2 ms 4352 KB
01_rnd_37.txt AC 2 ms 4352 KB
01_rnd_38.txt WA 23 ms 8444 KB
01_rnd_39.txt WA 23 ms 8444 KB