Submission #1123697

---

Source Code Expand

use std::io::{self, Stdin};
use std::str::{self, FromStr};
use std::error::Error;
use std::thread;
use std::collections::{BinaryHeap, HashSet};
use std::ops::{Add, Sub, Index, IndexMut};
use std::cmp::*;
// 座標
#[derive(Copy, Clone, Eq, Debug)]
struct Coord {
    x: i32,
    y: i32,
}
impl Coord {
    fn new(x_: i32, y_: i32) -> Coord {
        Coord { x: x_, y: y_ }
    }
}
impl Add for Coord {
    type Output = Coord; // Coord * Coord -> Coord
    fn add(self, other: Coord) -> Coord {
        Coord::new(self.x + other.x, self.y + other.y)
    }
}
impl Sub for Coord {
    type Output = Coord;
    fn sub(self, other: Coord) -> Coord {
        Coord::new(self.x - other.x, self.y - other.y)
    }
}
impl Ord for Coord {
    fn cmp(&self, other: &Coord) -> Ordering {
        let xcmp = self.x.cmp(&other.x);
        match xcmp {
            Ordering::Equal => self.y.cmp(&other.y),
            _ => xcmp,
        }
    }
}
impl PartialEq for Coord {
    fn eq(&self, other: &Coord) -> bool {
        self.x == other.x && self.y == other.y
    }
}
//全順序なのでこれでだいじょうぶ
impl PartialOrd for Coord {
    fn partial_cmp(&self, other: &Coord) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

const ROWS: usize = 51;
const COLS: usize = 51;
const ROWS_I: i32 = ROWS as i32;
const COLS_I: i32 = COLS as i32;
// ゲームマップ用の汎用型
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
struct Field<T> {
    data: Vec<Vec<T>>,
}
impl<T: Copy> Field<T> {
    fn new(init_num: T) -> Field<T> {
        let res = vec![vec![init_num; COLS + 2]; ROWS + 2];
        Field { data: res }
    }
}

impl<T> Index<Coord> for Field<T> {
    type Output = T;
    fn index(&self, id: Coord) -> &T {
        let col = id.x;
        let row = id.y;
        assert!(col >= 0 && row >= 0 && col <= COLS_I && row <= ROWS_I,
                "Index Error {:?}",
                id);
        &self.data[row as usize][col as usize]
    }
}

impl<T> Index<(i32, i32)> for Field<T> {
    type Output = T;
    fn index(&self, id: (i32, i32)) -> &T {
        let (col, row) = id;
        assert!(col >= 0 && row >= 0 && col <= COLS_I && row <= ROWS_I,
                "Index Error {:?}",
                id);
        &self.data[row as usize][col as usize]
    }
}

impl<T> IndexMut<Coord> for Field<T> {
    fn index_mut(&mut self, id: Coord) -> &mut T {
        let col = id.x;
        let row = id.y;
        assert!(col >= 0 && row >= 0 && col <= COLS_I && row <= ROWS_I,
                "Index Error {:?}",
                id);
        &mut self.data[row as usize][col as usize]
    }
}

impl<T> IndexMut<(i32, i32)> for Field<T> {
    fn index_mut<'a>(&'a mut self, id: (i32, i32)) -> &mut T {
        let (col, row) = id;
        assert!(col >= 0 && row >= 0 && col <= COLS_I && row <= ROWS_I,
                "Index Error {:?}",
                id);
        &mut self.data[row as usize][col as usize]
    }
}
fn print(f: &Field<u8>, n: i32) {
    for i in 0..n {
        for j in 0..n {
            print!("{}", f[(j + 1, i + 1)] as char);
        }
        println!("");
    }
}
const MOVES: [Coord; 4] =
    [Coord { x: 0, y: -1 }, Coord { x: -1, y: 0 }, Coord { x: 1, y: 0 }, Coord { x: 0, y: 1 }];
fn trim(field: &Field<u8>, n: i32) -> Field<u8> {
    let mut s = Field::new(b' ');
    for j in 1..n + 1 {
        let mut cur_y = n;
        for i in (1..n + 1).rev() {
            match field[(j, i)] {
                b'o' | b'x' => {
                    s[(j, cur_y)] = field[(j, i)];
                    cur_y -= 1;
                }
                b'-' => cur_y = i - 1,
                b'+' => cur_y -= 1,
                _ => {}
            }
        }
    }
    s
}
// scoring: O(N ^ 2)
fn score(field: &Field<u8>, n: i32) -> i32 {
    let s = trim(field, n);
    fn dfs(f: &Field<u8>, mut used: &mut Field<bool>, cur: Coord) -> i32 {
        used[cur] = true;
        let mut res = 1;
        for &m in &MOVES {
            let nxt = cur + m;
            if f[nxt] == f[cur] && used[nxt] == false {
                res += dfs(&f, &mut used, nxt);
            }
        }
        res
    }
    let mut used = Field::new(false);
    let (mut reso, mut resx) = (0, 0);
    for i in 1..n + 1 {
        for j in 1..n + 1 {
            if used[(j, i)] == true {
                continue;
            }
            if s[(j, i)] == b'o' {
                reso = max(reso, dfs(&s, &mut used, Coord::new(j, i)));
            }
            if s[(j, i)] == b'x' {
                resx = max(resx, dfs(&s, &mut used, Coord::new(j, i)));
            }
        }
    }
    reso + resx
}
#[derive(Clone)]
struct Search {
    field: Field<u8>,
    score: i32,
}
impl Ord for Search {
    fn cmp(&self, other: &Search) -> Ordering {
        self.score.cmp(&other.score)
    }
}
impl Eq for Search {}
impl PartialEq for Search {
    fn eq(&self, other: &Search) -> bool {
        self.score == other.score
    }
}
impl PartialOrd for Search {
    fn partial_cmp(&self, other: &Search) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
fn cross(xl: i32, xu: i32, yl: i32, yu: i32) -> bool {
    if yl < xu || xl < yu {
        return false;
    }
    true
}
fn search(init: &Field<u8>, n: i32) {
    let mut best = Search {
        field: init.clone(),
        score: score(&init, n),
    };
    let mut heap = BinaryHeap::new();
    heap.push(best.clone());
    let mut mp = HashSet::new();
    mp.insert(init.clone());
    const W: usize = 80;
    for j_ in 1..n {
        let mut cnt = 0;
        let mut nheap = BinaryHeap::new();
        while let Some(s) = heap.pop() {
            cnt += 1;
            if cnt == W {
                break;
            }
            let fld = s.field;
            let mut gs = Vec::new();
            for k in 0..2 {
                let mut stack: Vec<(u8, i32, i32)> = Vec::new();
                let j = j_ + k;
                let mut group = Vec::new();
                let mut cur_y = n;
                for i in (1..n + 1).rev() {
                    match fld[(j, i)] {
                        b'o' | b'x' => {
                            let do_pop = match stack.last() {
                                Some(p) => p.0 != fld[(j, i)],
                                None => false,
                            };
                            if do_pop {
                                let size = stack.len() as i32;
                                let start = stack[0].2;
                                let pos = stack[0].1;
                                group.push((stack[0].0, pos, start, size));
                                stack.clear();
                            }
                            stack.push((fld[(j, i)], i, cur_y));
                            cur_y -= 1;
                        }
                        b'-' | b'+' => {
                            if stack.is_empty() == false {
                                let size = stack.len() as i32;
                                let start = stack[0].2;
                                let pos = stack[0].1;
                                group.push((stack[0].0, pos, start, size));
                                stack.clear();
                            }
                            if fld[(j, i)] == b'-' {
                                cur_y = i - 1;
                            } else {
                                cur_y -= 1;
                            }
                        }
                        _ => {}

                    }
                }
                if stack.is_empty() == false {
                    let size = stack.len() as i32;
                    let start = stack[0].2;
                    let pos = stack[0].1;
                    group.push((stack[0].0, pos, start, size));
                    stack.clear();
                }
                gs.push(group);
            }
            for &(t1, pos1, low1, len1) in &gs[0] {
                for &(t2, pos2, low2, len2) in &gs[1] {
                    if t1 != t2 {
                        continue;
                    }
                    if low1 < low2 {
                        if pos2 + len2 - 1 > low1 {
                            continue;
                        }
                        let need = (low2 - len2 + 1) - low1;
                        let mut nfld = fld.clone();
                        let mut t = 0;
                        for i in (pos2..n + 1).rev() {
                            if t == need {
                                break;
                            }
                            if nfld[(j_ + 1, i)] == b'.' {
                                t += 1;
                                nfld[(j_ + 1, i)] = b'+';
                            }
                        }
                        if t < need {
                            let low1_top = low1 - len1 + 1;
                            let mut ok = false;
                            for i in pos2..n {
                                if nfld[(j_ + 1, i)] == b'.' || nfld[(j_ + 1, i)] == b'+' {
                                    if cross(low1_top, low1, i - len2, i - 1) {
                                        nfld[(j_ + 1, i)] = b'-';
                                        ok = true;
                                        break;
                                    }
                                }
                            }
                            if ok == false {
                                continue;
                            }
                        }
                        if mp.contains(&nfld) == false {
                            let scr = score(&nfld, n);
                            mp.insert(nfld.clone());
                            let ser = Search {
                                field: nfld,
                                score: scr,
                            };
                            if best.score < scr {
                                best = ser.clone();
                            }
                            nheap.push(ser);
                        }
                    } else if low1 > low2 {
                        if pos1 + len1 - 1 > low2 {
                            continue;
                        }
                        let need = (low1 - len1 + 1) - low2;
                        let mut nfld = fld.clone();
                        let mut t = 0;
                        for i in (pos1..n + 1).rev() {
                            if t == need {
                                break;
                            }
                            if nfld[(j_, i)] == b'.' {
                                t += 1;
                                nfld[(j_, i)] = b'+';
                            }
                        }
                        if t < need {
                            let low2_top = low2 - len2 + 1;
                            let mut ok = false;
                            for i in pos1..n {
                                if nfld[(j_, i)] == b'.' || nfld[(j_, i)] == b'+' {
                                    if cross(low2_top, low2, i - len1, i - 1) {
                                        nfld[(j_, i)] = b'-';
                                        ok = true;
                                        break;
                                    }
                                }
                            }
                            if ok == false {
                                continue;
                            }
                        }
                        if mp.contains(&nfld) == false {
                            let scr = score(&nfld, n);
                            mp.insert(nfld.clone());
                            let ser = Search {
                                field: nfld,
                                score: scr,
                            };
                            if best.score < scr {
                                best = ser.clone();
                            }
                            nheap.push(ser);
                        }
                    }
                }
            }
        }
        heap = nheap;
    }
    print(&best.field, n);
}
fn exec() {
    let mut sc = Scanner::new();
    let (field, n) = {
        let mut res = Vec::new();
        while let Some(s) = sc.next::<String>() {
            res.push(s.into_bytes());
        }
        let mut f = Field::new(b' ');
        let n = res.len() as i32;
        for i in 0..n {
            for j in 0..n {
                if res[i as usize][j as usize] == b'.' {
                    f[(j + 1, i + 1)] = b'.';
                } else {
                    f[(j + 1, i + 1)] = res[i as usize][j as usize];
                }
            }
        }
        (f, n)
    };
    search(&field, n);
}
fn main() {
    const DEFAULT_STACK: usize = 16 * 1024 * 1024;
    let builder = thread::Builder::new();
    let th = builder.stack_size(DEFAULT_STACK);
    let handle = th.spawn(|| { exec(); }).unwrap();
    let _ = handle.join();
}

#[allow(dead_code)]
struct Scanner {
    stdin: Stdin,
    id: usize,
    buf: Vec<u8>,
}

#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            id: 0,
            buf: Vec::new(),
        }
    }
    fn next_line(&mut self) -> Option<String> {
        let mut res = String::new();
        match self.stdin.read_line(&mut res) {
            Ok(0) => return None,
            Ok(_) => Some(res),
            Err(why) => panic!("error in read_line: {}", why.description()),
        }
    }
    fn next<T: FromStr>(&mut self) -> Option<T> {
        while self.buf.len() == 0 {
            self.buf = match self.next_line() {
                Some(r) => {
                    self.id = 0;
                    r.trim().as_bytes().to_owned()
                }
                None => return None,
            };
        }
        let l = self.id;
        assert!(self.buf[l] != b' ');
        let n = self.buf.len();
        let mut r = l;
        while r < n && self.buf[r] != b' ' {
            r += 1;
        }
        let res = match str::from_utf8(&self.buf[l..r]).ok().unwrap().parse::<T>() {
            Ok(s) => Some(s),
            Err(_) => {
                panic!("parse error, {:?}",
                       String::from_utf8(self.buf[l..r].to_owned()))
            }
        };
        while r < n && self.buf[r] == b' ' {
            r += 1;
        }
        if r == n {
            self.buf.clear();
        } else {
            self.id = r;
        }
        res
    }
    fn ne<T: FromStr>(&mut self) -> T {
        self.next::<T>().unwrap()
    }
}

Submission Info

Judge Result