로봇청소기 + 테스트케이스

2019/09/10 - [BOJ/C++] - [BOJ] 아맞다우산

[BOJ] 아맞다우산

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
 
#define INF 987654321
using namespace std;
 
int w, h;
char map[22][22];
typedef pair<int, int> pp;
bool visited[21][21];
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};
 
int bfs(pp p1, pp p2) {
    queue<pp> q;
    q.push(p1);
 
    memset(visited, 0, sizeof(visited));
    visited[p1.first][p1.second] = true;
 
    int res = INF, tmp = 0;
    while(!q.empty()) {
        int size = q.size();
        while(size--) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            if (x == p2.first && y == p2.second) {
                res = min(res, tmp);
                continue;
            }
 
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if (nx < 0 || nx >= h || ny < 0 || ny >= w || visited[nx][ny] || map[nx][ny] == 'x') continue;
 
                visited[nx][ny] = true;
                q.push(pp(nx, ny));
            }
        }
        ++tmp;
    }
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    while (1)
    {
        cin >> w >> h;
        if (w == 0 && h == 0) break;
 
        memset(map, 0, sizeof(map));
        vector<pp> pos;
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                cin >> map[i][j];
                if (map[i][j] == 'o') pos.insert(pos.begin(), pp(i, j));
                else if (map[i][j] == '*') pos.push_back(pp(i, j));
            }
        }
 
        int dp[22][22] = {{0}};
 
        for (int i = 0; i < pos.size(); i++) {
            for (int j = i; j < pos.size(); j++) {
                if (i == j) continue;
                dp[i][j] = dp[j][i] = bfs(pos[i], pos[j]);
            }
        }
        
        vector<int> seq;
        for (int i = 1; i < pos.size(); i++) {
            seq.push_back(i);
        }
 
        int ans = INF, sum, start;
        do {
            sum = 0; start = 0;
            bool flag =false;
            for (auto i : seq) {
                if (dp[start][i] == INF) {
                    flag = true;
                    break;
                }
                sum += dp[start][i];
                start = i;
            }
            if (flag) continue;
            ans = min(ans, sum);
 
        } while(next_permutation(seq.begin(), seq.end()));
 
        if (ans == INF) cout << -1 << '\n';
        else cout << ans << '\n';
    }
 
    return 0;
}
 

로봇청소기 TC.txt

0.02MB