글 읽기 - 아무리 해도 반례를 못 찾겠네요.

taehoon_gwon 6년 전 0

반례 있으신분 한 번 확인 부탁드려요...ㅠ

#include <iostream>
#include <cstring>
using namespace std;
int n,maxcnt=9,minmov,pinOfCnt[100],moveCnt[100];
char board[5][9];
bool pin[5][9];
const int dx[8]={0,1,1,1,0,-1,-1,-1};
const int dy[8]={1,1,0,-1,-1,-1,0,1};
bool possible(int x,int y,int xx,int yy){
    if(pin[x][y]){
        if(!pin[x+xx][y+yy] && board[x+xx][y+yy]=='.'){
            return true;
        }else{
            return false;
        }
    }else{
        return false;
    }
}
void Dfs(int gs,int step){
    if(gs==1) {
        maxcnt=1;
        minmov=step;
        return;
    }
    bool change =false;
    for(int i=0;i<5;i++) {
        for(int j=0;j<9;j++) {
            if(pin[i][j]){
                for(int k=0;k<8;k++) {
                    if(i+dx[k]<0 || i+dx[k]>4 || j+dy[k]<0 || j+dy[k]>8){
                        continue;
                    }else{
                        if(possible(i+dx[k], j+dy[k],dx[k],dy[k])){
                            change=true;
                            pin[i][j]=pin[i+dx[k]][j+dy[k]]=false;
                            board[i][j]=board[i+dx[k]][j+dy[k]]='.';
                            pin[i+2*dx[k]][j+2*dy[k]] = true;
                            board[i+2*dx[k]][j+2*dy[k]] ='o';
                            Dfs(gs-1,step+1);
                            pin[i][j]=pin[i+dx[k]][j+dy[k]]=true;
                            board[i][j]=board[i+dx[k]][j+dy[k]]='o';
                            pin[i+2*dx[k]][j+2*dy[k]] = false;
                            board[i+2*dx[k]][j+2*dy[k]]='.';
                        }
                    }
                }
            }
        }
    }
    if(!change) {
        if(gs<maxcnt){
            maxcnt=gs;
            minmov=step;
        }
        return;
    }
    return;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int gs=0;
        for(int j=0;j<5;j++) {
            for(int k=0;k<9;k++){
                cin>>board[j][k];
                if(board[j][k]=='o'){
                    pin[j][k]=true;
                    gs++;
                }
            }
        }
        printf("\n");
        Dfs(gs,0);
        pinOfCnt[i]=maxcnt;
        moveCnt[i]=minmov;
        maxcnt=8;
        memset(board, 0, 45);
        memset(pin, false, 45);
    }
    for(int i=0;i<n;i++) {
        printf("%d %d\n",pinOfCnt[i],moveCnt[i]);
    }
}

chungma900 6년 전 0

원문을 보면 The only legal move of a peg is a vertical or horizontal jump over an adjacent peg into the empty hole next to the jumped peg in line with it, which is then removed.

세로 또는 가로 방향으로만 핀을 넘어 빈칸으로 점프할수있다.

taehoon_gwon 6년 전 0

@chungma900 님 감사합니다 ㅎㅎ

아래 소스 처럼 바꿔보긴 했는데 답이 안나오는거 보니 제 코드가 문제인가 봐요..ㅎㅎ

const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

아무리 해도 반례를 못 찾겠네요.

taehoon_gwon 6년 전 0

chungma900 6년 전 0

taehoon_gwon 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말