hdu 5067 Harry And Dig Machine(dp)

제목 링크: hdu 5067 Harry And Dig Machine
제목 대의: 매트릭스를 정하고 처음에는 왼쪽 상단에 위치했다. 지금은 매트릭스에 있는 모든 0이 아닌 위치를 한 번 걷고 마지막에 왼쪽 상단으로 돌아가 가장 짧게 묻는다.
얼마나 걸립니까?
문제풀이 사고방식: 0이 아닌 위치는 최대 10을 넘지 않기 때문에 dp[s][i]로 s를 2진수로 어떤 위치가 지나갔는지 표시하고 i는 마지막에 머물렀던 위치를 나타낸다.

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;
const int maxn = 55;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> pii;

int N, M, g[maxn][maxn], dp[1<<12][12];
vector<pii> vec;

inline int dis(int i, int j) {
    return abs(vec[i].first - vec[j].first) + abs(vec[i].second - vec[j].second);
}

int solve () {

    int n = vec.size();
    int m = 1<<n;

    memset(dp, INF, sizeof(dp));
    dp[1][0] = 0;

    for (int i = 1; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i&(1<<j)) {
                for (int k = 0; k < n; k++)
                    dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j] + dis(j, k));
            }
        }
    }

    int ret = INF;
    for (int i = 0; i < n; i++)
        ret = min(ret, dp[m-1][i] + dis(0, i));
    return ret;
}

int main () {
    while (scanf("%d%d", &N, &M) == 2) {
        vec.clear();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                scanf("%d", &g[i][j]);
                if (g[i][j] || (i == 0 && j == 0))
                    vec.push_back(make_pair(i, j));
            }
        }
        printf("%d
", solve());
    }
    return 0;
}