글 읽기 - 반례를 찾는데 한계를 느꼈습니다 도아주십쇼 ....

sangwon98 2년 전 0

가능한 모든 테스트 케이스를 돌려봤지만 모두 정확한 답을 출력했습니다 ,하지만 9%에서 틀렸다고 하네요... 이유를 모르겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
const int MAX=8;
//cctv로 볼 수 있는 칸은 mark한다.
const int mark=-1;

int row,col,cctvsize,ans=21e8;

int office[MAX][MAX];
int cctv_state[MAX];

vector<int>cctv_kind;
vector<pair<int,int>>cctv_xy;

//각 cctv의 회전 정보를 기억하는 변수, 순서는 1~5번 순.

//시계 방향으로 회전
//1번 cctv는 모두 상하좌우 네 곳을 회전할 수 있기 때문에 1,2,3,4==상,하,좌,우 로 표현
//5번 cctv 같은 경우 네 방향으로 가기 때문에 회전 해봤자 항상 똑같다.
vector<vector<int>>cctv_twin={{1,2,3,4},{1,2},{1,2,3,4},{1,2,3,4},{1}};


//office의 정보를 담은 temp 배열과 좌표를 인자로 보낸다.
void up(int v[][MAX],int x,int y)
{
    if(x==0)return;
    for(int nx=x-1;nx>=0;--nx){
        //벽이라면 멈춘다.
        if(v[nx][y]==6)break;
        //오직 0일 때만 mark를 해준다.
        if(v[nx][y]==0)v[nx][y]=mark;
    }
}
void down(int v[][MAX],int x,int y)
{
    if(x==row-1)return;
    for(int nx=x+1;nx<row;++nx){
        if(v[nx][y]==6)break;
        if(v[nx][y]==0)v[nx][y]=mark;
    }
}
void left(int v[][MAX],int x,int y)
{
    if(y==0)return;
    for(int ny=y-1;ny>=0;--ny){
        if(v[x][ny]==6)break;
        if(v[x][ny]==0)v[x][ny]=mark;
    }
}
void right(int v[][MAX],int x,int y)
{
    if(y==col-1)return;
    for(int ny=y+1;ny<col;++ny){
        if(v[x][ny]==6)break;
        if(v[x][ny]==0)v[x][ny]=mark;
    }
}

//모든 경로 탐색
void func(int lev)
{
    //모든 cctv의 뱡향을 정했을 때.
    if(lev==cctvsize)
    {
        int cnt=0;
        int temp[MAX][MAX];
        for(int i=0;i<row;++i)
        {
            for(int j=0;j<col;++j){
                temp[i][j]=office[i][j];
            }
        }
        //cctv의 종류,선택된 방향,그리고 좌표를 이용해 처리해준다
        for(int i=0;i<cctvsize;++i)
        {
            //cctv의 종류가 1번일 때.
            if(cctv_kind[i]==1)
            {
                //회전 방향이 위일 때
                if(cctv_state[i]==1)up(temp,cctv_xy[i].first,cctv_xy[i].second);
                //오른쪽일 때
                else if(cctv_state[i]==2)right(temp,cctv_xy[i].first,cctv_xy[i].second);
                //아랫쪽 일 때
                else if(cctv_state[i]==3)down(temp,cctv_xy[i].first,cctv_xy[i].second);
                //왼쪽일 때
                else if(cctv_state[i]==4)left(temp,cctv_xy[i].first,cctv_xy[i].second);
            }

            else if(cctv_kind[i]==2)
            {
                if(cctv_state[i]==1)
                {
                    left(temp,cctv_xy[i].first,cctv_xy[i].second);
                    right(temp,cctv_xy[i].first,cctv_xy[i].second);
                }
                else if(cctv_state[i]==2)
                {
                    up(temp,cctv_xy[i].first,cctv_xy[i].second);
                    down(temp,cctv_xy[i].first,cctv_xy[i].second);
                }
            }

            else if(cctv_kind[i]==3)
            {
                if(cctv_state[i]==1)
                {
                    up(temp,cctv_xy[i].first,cctv_xy[i].second);
                    right(temp,cctv_xy[i].first,cctv_xy[i].second);
                }
                else if(cctv_state[i]==2)
                {
                    right(temp,cctv_xy[i].first,cctv_xy[i].second);
                    down(temp,cctv_xy[i].first,cctv_xy[i].second);
                }
                else if(cctv_state[i]==3)
                {
                    left(temp,cctv_xy[i].first,cctv_xy[i].second);
                    down(temp,cctv_xy[i].first,cctv_xy[i].second);
                }
                else if(cctv_state[i]==4)
                {
                    left(temp,cctv_xy[i].first,cctv_xy[i].second);
                    up(temp,cctv_xy[i].first,cctv_xy[i].second);
                }
            }

            else if(cctv_kind[i]==4)
            {
                if(cctv_state[i]==1)
                {
                    up(temp,cctv_xy[i].first,cctv_xy[i].second);
                    left(temp,cctv_xy[i].first,cctv_xy[i].second);
                    right(temp,cctv_xy[i].first,cctv_xy[i].second);
                }
                else if(cctv_state[i]==2)
                {
                    up(temp,cctv_xy[i].first,cctv_xy[i].second);
                    right(temp,cctv_xy[i].first,cctv_xy[i].second);
                    down(temp,cctv_xy[i].first,cctv_xy[i].second);
                }
                else if(cctv_state[i]==3)
                {
                    left(temp,cctv_xy[i].first,cctv_xy[i].second);
                    right(temp,cctv_xy[i].first,cctv_xy[i].second);
                    down(temp,cctv_xy[i].first,cctv_xy[i].second);
                }
                else if(cctv_state[i]==4)
                {
                    right(temp,cctv_xy[i].first,cctv_xy[i].second);
                    up(temp,cctv_xy[i].first,cctv_xy[i].second);
                    down(temp,cctv_xy[i].first,cctv_xy[i].second);
                }
            }

            else if(cctv_kind[i]==5)
            {
                up(temp,cctv_xy[i].first,cctv_xy[i].second);
                down(temp,cctv_xy[i].first,cctv_xy[i].second);
                left(temp,cctv_xy[i].first,cctv_xy[i].second);
                right(temp,cctv_xy[i].first,cctv_xy[i].second);
            }
        }
        //사각지대의 갯수를 파악한다.
        //cctv로 볼 수 있는 칸은 mark로 설정했기에 칸이 0일 때만 ++cnt를 해준다.
        for(int i=0;i<row;++i)for(int j=0;j<col;++j)if(temp[i][j]==0)++cnt;
        //작을 때 마다 ans의 값을 바꿔준다.
        ans= min(ans,cnt);
        return;
    }
    //office 배열에서 1~5사이 cctv종류가 나오면 cctv_kind,cctv_xy에 cctv종류와 해당 좌표를 추가했다.
    //따라서 cctv_kind[lev]의 종류에 따라 회전 가능한 범위가 달라진다.
    //ex))cctv_kind[lev]-1이 0이라면 cctv의 종류는 1번, 총 {1,2,3,4} 상하좌우로 움직일 수 있다
    //{1,2,3,4}중 하나를 선택해서 cctv_state에 넣고 다음 함수를 호출한다.
    for(int i=0;i<cctv_twin[cctv_kind[lev]-1].size();++i)
    {
        int dir=cctv_twin[cctv_kind[lev]-1][i];
        cctv_state[lev]=dir;
        func(lev+1);
        cctv_state[lev]=0;
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>row>>col;
    for(int i=0;i<row;++i){
        for(int j=0;j<col;++j){
            cin>>office[i][j];
            if(office[i][j]>=1&&office[i][j]<=5){
                //cctv라면 해당 종류와 좌표를 넣어준다.
                cctv_kind.emplace_back(office[i][j]);
                cctv_xy.emplace_back(i,j);
            }
        }
    }
    //cctv의 갯수 파악하기.
    cctvsize=cctv_kind.size();

    func(0);
    cout<<ans;
    return 0;
}

kdh6429 2년 전 0

cctv kind 가 4일때, 2, 4 상태의 방향이 같은 것 같습니다. 한참봤네요 ^^;

else if(cctv_state[i]==2)

{

up(temp,cctv_xy[i].first,cctv_xy[i].second);

right(temp,cctv_xy[i].first,cctv_xy[i].second);

down(temp,cctv_xy[i].first,cctv_xy[i].second);

}

else if(cctv_state[i]==3)

{

...

}

else if(cctv_state[i]==4)

{

right(temp,cctv_xy[i].first,cctv_xy[i].second);

up(temp,cctv_xy[i].first,cctv_xy[i].second);

down(temp,cctv_xy[i].first,cctv_xy[i].second);

}

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

문제

문제

출처

ICPC

반례를 찾는데 한계를 느꼈습니다 도아주십쇼 ....

sangwon98 2년 전 0

kdh6429 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말