[BOJ-5558]치~즈

http://acmicpc.net/problem/5558

[풀이방법]

여러번의 BFS로 풀이할 수 있는 문제

사실상 몇개의 치즈를 먹어야 하는지 주어지지만 필요없이 풀 수가 있다.

정렬을 이용한 방법으로 풀 수 있는 방법.

[C++11]

#include<cstdio>
#include<queue>
#include<memory.h>
#include<vector>
#include<algorithm>
using namespace std;
 
const int dr[] = { 0,0,-1,1 };
const int dc[] = { -1,1,0,0 };
const int m = 1111;
 
struct pos {
    int r, c;
    int number;
    pos() {}
    pos(int ir, int ic) :r(ir), c(ic) {}
    pos(int ir, int ic, char inum) :r(ir), c(ic), number(inum - '0') {}
};
 
bool cmp(pos& a, pos& b) {
    if (a.number < b.number) return true;
    return false;
}
 
vector<pos> v;
char im[m][m];
int vis[m][m];
 
int main() {
    int row, col, need;
    scanf("%d%d", &row, &col);
    scanf("%d", &need);
    pos start;
    for (int r = 0; r < row; r++) {
        scanf("%s", im[r]);
        for (int c = 0; c < col; c++) {
            if (im[r][c] == 'S') v.push_back(pos(r, c, '0'));
            else if ('1' <= im[r][c] && im[r][c] <= '9') v.push_back(pos(r, c, im[r][c]));
        }
    } // input
 
    sort(v.begin(), v.end(), cmp);
 
    int ans = 0;
    for (int i = 0; i < v.size() - 1; i++) {
        memset(vis, -1, sizeof(vis));
 
        queue<pos> Q = queue<pos>();
        Q.push(v[i]);
        vis[v[i].r][v[i].c] = 0;
        bool is_ok = false;
        while (!Q.empty()) {
            pos here = Q.front();
            Q.pop();
            int hr = here.r;
            int hc = here.c;
 
            if (is_ok) break; // find dst!
 
            for (int di = 0; di < 4; di++) {
                int tr = hr + dr[di];
                int tc = hc + dc[di];
 
                if (tr < 0 || row <= tr || tc < 0 || col <= tc) continue;
                if (vis[tr][tc] != -1) continue;
                if (im[tr][tc] == 'X') continue;
 
                vis[tr][tc] = vis[hr][hc] + 1;
                Q.push(pos(tr, tc));
                if (tr == v[i + 1].r && tc == v[i + 1].c) {
                    ans += vis[tr][tc];
                    is_ok = true;
                }
            }
        } // i-th BFS        
    }
    printf("%d\n", ans);
    return 0;
}