글 읽기 - 12퍼에서 틀렸습니다가 뜹니다..

skseofhek 4년 전 0

dfs함수에서 5번째까지 방향을 찾아서 d[]에 넣어주었고,

5번째가 되었을 때, 각 방향만큼 bmove() 함수로 방향을 이동했습니다.

방향을 이동하는 bmove()에서 뭔가 이상한 것이 있을것 같은데

어디가 잘못되었을까요...?

방향은 0, 1, 2, 3 순서로 오른쪽, 위쪽, 왼쪽, 아래쪽 입니다.

#include <iostream>

#include <cstring>

using namespace std;

int N;
long long ret;
long long map[20][20];
long long tmap[20][20];
int d[6];

void bmove(int dir)
{
    if(dir == 0)
    {
        for(int y=0; y<N; y++)
        {
            long long ytmp[20] = {0, };
            int nidx = N-1;
            while(tmap[y][nidx] == 0)
                nidx--;
            //printf("%d \n", nidx);
            if(nidx >= 0)
                ytmp[N-1] = tmap[y][nidx];
            int cidx = N-2;

            for(int x = nidx-1; x>=0; x--)
            {
                if(tmap[y][x] != 0)
                {
                    ytmp[cidx] = tmap[y][x];
                    if(ytmp[cidx] == ytmp[cidx + 1])
                    {
                        ytmp[cidx+1] *= 2;
                        ytmp[cidx] = 0;
                        if(x-1 >= 0 && tmap[y][x-1] != 0)
                        {
                            ytmp[cidx] = tmap[y][x-1];
                            //printf("%d %d\n", x-1, map[y][x-1]);
                            x--;
                            cidx--;
                        }
                    }
                    else
                    {
                        cidx--;   
                    }
                }
            }

            for(int x=0; x<N; x++)
            {
                tmap[y][x] = ytmp[x];
            }
        }
    }
    else if(dir == 1)
    {
        for(int x = 0; x<N; x++)
        {
            long long xtmp[20] = {0, };
            int nidx = 0;
            while(tmap[nidx][x] == 0)
                nidx++;
            if(nidx < N)
                xtmp[0] = tmap[nidx][x];

            int cidx = 1;

            for(int y = nidx+1; y<N; y++)
            {
                if(tmap[y][x] != 0)
                {
                    xtmp[cidx] = tmap[y][x];
                    //printf("%d %d\n", y, map[y][x]);
                    if(xtmp[cidx] == xtmp[cidx-1])
                    {
                        xtmp[cidx-1] *= 2;
                        xtmp[cidx] = 0;
                        if(y+1 < N && tmap[y+1][x] != 0)
                        {
                            xtmp[cidx] = tmap[y+1][x];
                            y++;
                            cidx++;
                        }
                    }
                    else
                    {
                        cidx++;
                    }   
                }
            }

            for(int y = 0; y<N; y++)
            {
                tmap[y][x] = xtmp[y];
            }
        }
    }
    else if(dir == 2)
    {
        for(int y=0; y<N; y++)
        {
            long long ytmp[20] = {0, };
            int nidx = 0;
            while(tmap[y][nidx] == 0)
                nidx++;
            //printf("%d \n", nidx);
            if(nidx < N)
                ytmp[0] = tmap[y][nidx];
            int cidx = 1;

            for(int x = nidx+1; x<N; x++)
            {
                if(tmap[y][x] != 0)
                {
                    ytmp[cidx] = tmap[y][x];
                    if(ytmp[cidx] == ytmp[cidx - 1])
                    {
                        ytmp[cidx-1] *= 2;
                        ytmp[cidx] = 0;
                        if(x+1 < N && tmap[y][x+1] != 0)
                        {
                            ytmp[cidx] = tmap[y][x+1];
                            //printf("%d %d\n", x-1, map[y][x-1]);
                            x++;
                            cidx++;
                        }
                    }
                    else
                    {
                        cidx++;   
                    }
                }
            }

            for(int x=0; x<N; x++)
            {
                tmap[y][x] = ytmp[x];
            }
        }
    }
    else if(dir == 3)
    {
        for(int x = 0; x<N; x++)
        {
            long long xtmp[20] = {0, };
            int nidx = N-1;
            while(tmap[nidx][x] == 0)
                nidx--;
            if(nidx >= 0)
                xtmp[N-1] = tmap[nidx][x];
            int cidx = N-2;

            for(int y = nidx-1; y>=0; y--)
            {
                if(tmap[y][x] != 0)
                {
                    xtmp[cidx] = tmap[y][x];
                    if(xtmp[cidx] == xtmp[cidx+1])
                    {
                        xtmp[cidx+1] *= 2;
                        xtmp[cidx] = 0;
                        if(y-1 >= 0 && tmap[y-1][x] != 0)
                        {
                            xtmp[cidx] = tmap[y-1][x];
                            y--;
                            cidx--;
                        }
                    }
                    else
                    {
                        cidx--;
                    }
                }
            }

            for(int y = 0; y<N; y++)
            {
                tmap[y][x] = xtmp[y];
            }
        }
    }
}

void dfs(int dep, int cur)
{
    if(dep == 5)
    {
        memset(tmap, 0, sizeof(long long)*20*20);
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                tmap[i][j] = map[i][j];
            }
        }

        for(int i=0; i<5; i++)
        {
            //printf("d[%d] = %d ", i, d[i]);
            bmove(d[i]);
        }

        long long tret = 0;

        //printf("\n");
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                //printf("%d ", map[i][j]);
                if(tret < tmap[i][j])
                    tret = tmap[i][j];
            }
            //printf("\n");
        }

        if(tret > ret)
            ret = tret;

        return;
    }

    for(int i=0; i<4; i++)
    {
        if(i != cur)
        {
            d[dep] = i;
            dfs(dep+1, i);
        }
    }
}

void print_arr(void)
{
    printf("\n");
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            printf("%lld ", map[i][j]);
        }
        printf("\n");
    }
}

int main(void)
{
    scanf("%d", &N);

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            scanf("%lld", &map[i][j]);
        }
    }

    dfs(0, -1);
/*    
    bmove(0);
    print_arr();
    bmove(1);
    print_arr();
    bmove(0);
    print_arr();
    bmove(1);
    print_arr();
    bmove(0);
    print_arr();

    printf("\n");
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
*/
    printf("%lld\n", ret);

    return 0;
}

eodlsgh123 3년 전 0

안녕하세요 저도 12 % 에서 틀렸다고 나오는데

지금은 해결 하셧나요 ? 혹시 해결하셧으면 12 % 반례를 알 수 있을가요 ? ㅠ

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

문제

문제

출처

ICPC

12퍼에서 틀렸습니다가 뜹니다..

skseofhek 4년 전 0

eodlsgh123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말