1249 보급로

연합군 독인군 전투가 치열해짐

출발지에서 도착지 까지 가기 위한 도로 복구 작업 빠른 시간 내 수행하려고 함

깊이 비례하여 복구 시간은 증가함

출발지에서 도착지로 가는 경로 중 복구 시간이 가장 짧은 경로에 대한 총 복구 시간 구하기

깊이가 1 복구 시간 1 

 

지도 정보 2차원 배열

좌상단 칸 우하단 칸 상하좌우 방향 한 칸 씩움직일 수 있음

 

#include<stdio.h> // 헤더 파일
#define M 90001 // 왜 엠을 넣엇지?
int n; // 
char a[1009][1009];
int d[1009][1009];
struct A { // 구조체 사용 노드 사용
    A *next;
    int i, j;
};
A *q[M]; 
A *r[M];
A *make(int si, int sj)
{
    A *me = new A();
    me->i = si;
    me->j = sj;
    me->next = NULL;
    return me;
}
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int main()
{
    int t, tv = 0;
    int i, j, k, l;
    scanf("%d", &t); // 테케
    while (t--)
    {
        int s = 0;
        scanf("%d", &n); // 크기
        for (i = 0; i < n; i++)
        {
            scanf("%s", a[i]); // 문자열이므로 s 로 입력을 받고
            for (j = 0; j < n; j++)
                s += a[i][j] - '0'; 
        }
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                d[i][j] = 999999; // 디피로 풀이?
        for (i = 0; i <= s; i++)
            q[i] = r[i] = 0;
        q[0] = make(0, 0);
        r[0] = q[0];
        d[0][0] = 0;
        for (i = 0; i <= s; i++)
        {
            while (q[i])
            {
                int qi = q[i]->i;
                int qj = q[i]->j;
                A *me = q[i];
                q[i] = q[i]->next;
                for (k = 0; k < 4; k++)
                {
                    int ti = qi + dx[k];
                    int tj = qj + dy[k];
                    if (ti >= 0 && ti<n)
                        if (tj >= 0 && tj < n)
                        {
                            if (d[ti][tj] > d[qi][qj] + a[ti][tj] - '0')
                            {
                                d[ti][tj] = d[qi][qj] + a[ti][tj] - '0';
                                int tk = d[ti][tj];
                                if (r[tk] == NULL)
                                {
                                    q[tk] = make(ti, tj);
                                    r[tk] = q[tk];
                                }
                                else
                                {
                                    r[tk]->next = make(ti, tj);
                                    r[tk] = r[tk]->next;
                                }
                                if (q[tk] == NULL)
                                {
                                    q[tk] = r[tk];
                                }
                            }
                        }
                }
                delete me;
            }
        }
        printf("#%d %d\n", ++tv, d[n - 1][n - 1]);
    }
}