Submission #7496

#	Time	Username	Problem	Language	Result	Execution time	Memory
7496		baneling100	배열 탈출 (GA8_array)	C++98	49 / 100	2000 ms	40200 KiB

array

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 0x7fffffff

using namespace std;

typedef pair <int,int> ppair;
typedef pair <int,ppair> pppair;
priority_queue <pppair,vector<pppair>,greater<pppair> > Q;
int N, A[2223][2223], D[2223][2223];

void input(void)
{
    int i, j;

    scanf("%d",&N);
    for(i=1 ; i<=N ; i++)
        for(j=1 ; j<=N ; j++)
        {
            scanf("%d",&A[i][j]);
            D[i][j]=INF;
        }
}

void process(void)
{
    int i, y, x, ty, tx;

    D[1][1]=0;
    Q.push(make_pair(0,make_pair(1,1)));
    while(!Q.empty())
    {
        y=Q.top().second.first;
        x=Q.top().second.second;
        Q.pop();
        ty=y;
        tx=x+1;
        if(ty>=1 && ty<=N && tx>=1 && tx<=N)
        {
            if(A[y][x]>A[ty][tx])
            {
                if(D[ty][tx]>D[y][x])
                {
                    D[ty][tx]=D[y][x];
                    Q.push(make_pair(D[ty][tx],make_pair(ty,tx)));
                }
            }
            else
                if(D[ty][tx]>D[y][x]+A[ty][tx]-A[y][x]+1)
                {
                    D[ty][tx]=D[y][x]+A[ty][tx]-A[y][x]+1;
                    Q.push(make_pair(D[ty][tx],make_pair(ty,tx)));
                }
        }
        ty=y+1;
        tx=x;
        if(ty>=1 && ty<=N && tx>=1 && tx<=N)
        {
            if(A[y][x]>A[ty][tx])
            {
                if(D[ty][tx]>D[y][x])
                {
                    D[ty][tx]=D[y][x];
                    Q.push(make_pair(D[ty][tx],make_pair(ty,tx)));
                }
            }
            else
                if(D[ty][tx]>D[y][x]+A[ty][tx]-A[y][x]+1)
                {
                    D[ty][tx]=D[y][x]+A[ty][tx]-A[y][x]+1;
                    Q.push(make_pair(D[ty][tx],make_pair(ty,tx)));
                }
        }
    }
}

void output(void)
{
    printf("%d",D[N][N]);
}

int main(void)
{
    input();
    process();
    output();

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 11 / 11
• Subtask 3: 32 / 32
• Subtask 4: 0 / 51