[백준 33562] shapex

티어: 플5

 

제 2회 유틸컵 당시 7솔 배경을 눈앞에 두고 막힌 통곡의 벽 같은 문제를 드디어 풀었다. 풀고 보니 대회때도 충분히 풀 수 있었을 것 같은데.. 아쉽다.

 

결합기를 제외한 나머지 기계는 상대적으로 구현이 쉽다. 결합기를 어떻게 만들어야할까?

대회 당시 코드를 보니 결합기를 실제로 시뮬레이션 하려고 매우 길고 복잡한 casework를 했었었다.

하지만 경우의 수는 그리 많치 않은데, 몇칸 결합될 수 있는지만 알면 되기 때문이다.

기본 도형을 a, a위에서 아래로 내려가며 결합할 도형을 b라고 하자.

모든 도형을 실제 높이에 상관없이 빈 줄을 추가해 4줄로 맞춰준다면 구현이 편리해진다.

결합기의 역할은 a와 b가 겹치지 않는 선에서 최대한 b를 내려주는것이고, 각 경우에 대해 고려해야하는 모든것을 적어보자.

i. 1줄을 내리려면 a의 4층과 b의 1층이 안겹치면 된다.

ii. 2줄을 내리려면 i조건에 추가로 a의 3층과 b의 1층이 안겹쳐야 하고, a의 4층과 b의 2층이 안겹쳐야한다.

iii. 3줄을 내리려면 ii조건에 추가로 a의 2층과 b의 1층이 안겹쳐야 하고...

iiii. 4줄을 내리려면 iii조건에 추가로 a의 1층과 b의 1층이...

이것만 처리해주면 결합기와 같은 역할을 해줄 수 있다.

 

var input = require('fs').readFileSync(0,'utf8').trim().split('\n')
var [n, m] = input[0].split(' ').map(Number)
var r = [...Array(101)].map(e => 0)
var color = ['r', 'g', 'b', 'y', 'p', 'c', 'w', 'u']

function J(i,j,k) { //절단기
    if(r[i] == 0) {
        r[j] = 0
        r[k] = 0
    }else {
        var s = r[i].split(':')
        r[j] = s.map(e => '----' + e.slice(4)).filter(e => e != '--------').join(':')
        r[k] = s.map(e => e.slice(0,4) + '----').filter(e => e != '--------').join(':')
        if(r[j] === '') r[j] = 0
        else if(r[k] === '') r[k] = 0
    }

}

function H(i,j,k) { //회전기
    if(r[i] == 0) r[j] = 0
    else if(k == 1) {
        r[j] = r[i].split(':').map(e => e.slice(-2) + e.slice(0, -2)).join(':')
    }else if(k == 2) {
        r[j] = r[i].split(':').map(e => e.slice(4) + e.slice(0, 4)).join(':')
    }else {
        r[j] = r[i].split(':').map(e => e.slice(2) + e.slice(0, 2)).join(':')
    }
}

function G(i, j, k) { //결합기
    if(r[i] == 0 || r[j] == 0) {
        r[k] = 0
        return
    }
    var a = r[i].split(':')
    a.push('--------')
    a.push('--------')
    a.push('--------')
    a.push('--------')
    var b = r[j].split(':')
    b.push('--------')
    b.push('--------')
    b.push('--------')
    b.push('--------')
    a = a.slice(0,4)
    b = b.slice(0,4)
    var dab = a
    var deep = 0
    /*
    a3과 b0
    a2와 b0, a3과 b1
    a1과 b0, a2와 b1, a3와 b2
    a0와 b0, a1와 b1, a2와 b2, a3와 b3
    */
    if(GG(a[3],b[0])) {
        deep++
        if(GG(a[2],b[0])&&GG(a[3],b[1])) {
            deep++
            if(GG(a[1],b[0])&&GG(a[2],b[1])&&GG(a[3],b[2])) {
                deep++
                if(GG(a[0],b[0])&&GG(a[1],b[1])&&GG(a[2],b[2])&&GG(a[3],b[3]))
                    deep++
            }
        }
    }
    switch(deep) {
        case 1:
            dab[3] = GH(a[3],b[0])
            break
        case 2:
            dab[2] = GH(a[2],b[0])
            dab[3] = GH(a[3],b[1])
            break
        case 3:
            dab[1] = GH(a[1],b[0])
            dab[2] = GH(a[2],b[1])
            dab[3] = GH(a[3],b[2])
            break
        case 4:
            dab[0] = GH(a[0],b[0])
            dab[1] = GH(a[1],b[1])
            dab[2] = GH(a[2],b[2])
            dab[3] = GH(a[3],b[3])
            break
    }
    dab = dab.filter(e=>e!='--------')
    r[k]=dab.join(':')||0
}

function GG(s1,s2) { //층 결합 가능 여부 판단
    for(var i = 0; i < 8; i++) {
        if(s1[i]!='-'&&s2[i]!='-') return false
    }
    return true
}

function GH(s1,s2) { //층 결합
    var C = ''
    for(var i = 0; i < 8; i++) C+=s1[i]!='-'?s1[i]:s2[i]
    return C
}

function S(i,j,k) { //색칠기
    if(r[i] == 0) r[j] = 0
    else r[j] = r[i].replace(new RegExp(color.join('|'), 'g'), k)
}

for(var i = 1; i <= n; i++) r[i] = input[i]
for(var i = n+1; i <= n+m; i++) {
    var q = input[i].split(' ')
    switch (+q[0]) {
        case 1:
            J(+q[1],+q[2],+q[3])
            break
        case 2:
            H(+q[1],+q[2],+q[3])
            break
        case 3:
            G(+q[1],+q[2],+q[3])
            break
        case 4:
            S(+q[1],+q[2],q[3])
            break
    }
}

console.log(r[100]==0?'None':r[100])
//console.log(r.join('\n'))