티스토리 뷰

문제: icpc.me/1445


꽃을 통과하는 경우를 최소로 하고 싶고 꽃을 통과하는 경우의 최소가 여러경로가 존재할 때 꽃의 옆을 지나가는 경우를 최소로 하고 싶을 때 최단경로를 찾는 문제이다.


우선이 되는 꽃을 통과하는 경우에 나올 수 있는 최대 꽃의 수 2500보다 큰값을 곱해서 cost를 주고 꽃의 옆을 지나가는 경우를 1로 준 뒤 다익스트라를 돌린 후 곱한 값을 나눈 값과 나머지를 출력해주면 된다.


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int n, m, dp[55][55], g[55][55], sx, sy, ex, ey;
char a[55][55];
int dx[] = { 0,0,1,-};
int dy[] = { 1,-1,0,};
int chk(int x, int y) {
    return <= x&&< n && <= y&&< m;
}
int main() {
    scanf("%d%d"&n, &m);
    for (int i = 0; i < n; i++) {
        getchar();
        for (int j = 0; j < m; j++) {
            scanf("%c"&a[i][j]);
            if (a[i][j] == 'S')
                sx = i, sy = j;
            else if (a[i][j] == 'F')
                ex = i, ey = j;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'g')
                g[i][j] = 3000;
            else if (a[i][j] == '.') {
                int f = 0;
                for (int k = 0; k < 4; k++) {
                    if (chk(i + dx[k], j + dy[k]) && a[i + dx[k]][j + dy[k]] == 'g')
                        f = 1;
                }
                if (f)g[i][j] = 1;
            }
        }
    }
    memset(dp, -1sizeof(dp));
    priority_queue<pair<int, pair<intint>>> pq;
    pq.push({ g[sx][sy],{sx,sy} });
    while (pq.size()) {
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        int cost = -pq.top().first;
        pq.pop();
        if (dp[x][y] != -1)continue;
        dp[x][y] = cost;
        for (int i = 0; i < 4; i++) {
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (!chk(cx, cy) || dp[cx][cy] != -1)continue;
            pq.push({ -cost - g[cx][cy],{cx,cy} });
        }
    }
    printf("%d %d\n", dp[ex][ey] / 3000, dp[ex][ey] % 3000);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14426 접두사 찾기  (0) 2017.08.04
BOJ)1938 통나무 옮기기  (0) 2017.08.03
BOJ)1445 일요일 아침의 데이트  (11) 2017.08.03
BOJ)10256 돌연변이  (0) 2017.08.03
BOJ)9250 문자열 집합 판별  (0) 2017.08.02
BOJ)1063 킹  (0) 2017.08.02
댓글
  • 프로필사진 hoon222y 일요일 날 데이트 하시나요? 2017.08.05 15:54 신고
  • 프로필사진 JASON 자손9319 좀 해보고 싶네요 ^^ 2017.08.06 16:00 신고
  • 프로필사진 질문! 혹시 Bitonic tour 알고리즘 설명 해주 실 수 있으신가요???ㅠㅠ 이해가 안가요!!전혀 이문제랑 관련없지만요! 2017.08.17 15:25
  • 프로필사진 JASON 자손9319 바이토닉 투어 개념을 말씀하시는건지 아니면 변형된 바이토닉 투어 문제들을 말씀을 하시는건지 모르겠네요 ㅠㅠ.. 우선 tsp문제는 NP문제인데 특정 조건이 붙으면 다항시간에 해결할 수 있어요
    이 때 특정 조건은 모든 도시를 순회할건데 한 방향으로 임의의 도시들을 순회하고 돌아오면서 나머지 임의의 도시들을 순회하는 방식으로 해결하면 N^2 dp로 해결할 수 있어요 ㅠㅠ.. 도움이 안될거같지만..
    2017.08.17 21:52 신고
  • 프로필사진 질문! 그냥 말씀드리면, https://www.acmicpc.net/problem/10272
    이 문제를 풀고싶습니다!

    그래서 bitonic tour라고 검색을 해서 나온 블로그를 읽어보았는데 이해가 가지 않아서요 ㅠㅠ

    그래서 자손님에게 큰 요청을 드립니다!

    (수정) 아! 개념과 문제 적용을...
    2017.08.18 22:28
  • 프로필사진 JASON 자손9319 으어 저도 아직 안 푼 문제군요 ㅋㅋ... 개념이라고하면.. 바이토닉 투어 자체는 구글링 해보시면 나올거에요 근데 아마 지금 푸시려는게 10272 같은 변형 된 바이토닉 투어 문제니까 .. 문제를 읽어보면 바이토닉 투어라는걸 알 수 있고 그래서 n^2 dp로 접근을 할 수 있는거죠 ㅠㅠ 저는 변형된 바이토닉 투어 문제에서 정형화 된 틀에서 코딩하지는 않고.. 그냥 n^2 dp로 해결한다고만 생각하고 코딩하는 편이라서 ㅠㅠ 많은 도움은 못드리겠네요 http://jason9319.tistory.com/291 이 문제 한번 읽어보시면 조금 도움이 될 거같아요 ㅠㅠㅠ 2017.08.18 23:44 신고
  • 프로필사진 JASON 자손9319 점화식 세울 때 팁을 드리자면 보통 dp[l][r]이 l은 갈 때 커버 r은 올 때 커버가 될 거에요 이렇게 테이블 잡고 r은 역방향에서 온다는거만 신경써주시면 될 거같아요 ㅠㅠ 2017.08.18 23:46 신고
  • 프로필사진 JASON 자손9319 http://jason9319.tistory.com/336 에 해당 문제 풀이를 올렸습니다 ㅠㅠ 2017.08.19 13:03 신고
  • 프로필사진 질문! 자손님은사랑입니다 2017.08.20 10:26
  • 프로필사진 smu201111192 자손님 팬이에용~
    2017.08.30 15:25
  • 프로필사진 JASON 자손9319 헐.. 이 누추한곳에.. 영광입니다 2017.08.30 21:29 신고
댓글쓰기 폼