hihocoder #1608 : Jerry的奶酪（状压dp）

题目链接：http://hihocoder.com/problemset/problem/1608

题解：就是一道简单的状压dp由于dfs过程中只需要几个点之间的转移所以只要预处理一下几个点就行。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
int dp[1 << 11];
int to[333][333] , dr[4][2] = {1 , 0 , -1 , 0 , 0 , 1 , 0 , -1};
char mmp[333][333];
int n , m , k;
struct TnT {
    int x , y , step;
}point[12];
bool vis[333][333];
int bfs(TnT sta , TnT ed) {
    queue<TnT>q;
    memset(vis , false , sizeof(vis));
    sta.step = 0;
    q.push(sta);
    vis[sta.x][sta.y] = true;
    while(!q.empty()) {
        TnT gg = q.front();
        q.pop();
        if(gg.x == ed.x && gg.y == ed.y) return gg.step;
        for(int i = 0 ; i < 4 ; i++) {
            TnT gl = gg;
            gl.x += dr[i][0];
            gl.y += dr[i][1];
            gl.step++;
            if(gl.x >= 0 && gl.x < n && gl.y >= 0 && gl.y < m && mmp[gl.x][gl.y] != '1' && !vis[gl.x][gl.y]) {
                vis[gl.x][gl.y] = true;
                q.push(gl);
            }
        }
    }
    return -1;
}
int ans;
void dfs(int state , int numb , int step) {
    if(state == -1) return ;
    TnT sta , ed;
    sta = point[numb];
    if(state == (1 << k) - 1) {
        ed = point[k + 1];
        if(to[numb][k + 1] == -1) return ;
        if(ans == -1) {
            ans = step + to[numb][k + 1];
        }
        else ans = min(ans , step + to[numb][k + 1]);
        return ;
    }
    for(int i = 0 ; i < k ; i++) {
        int g = (1 << i);
        if(state & g) continue;
        TnT ed = point[i];
        int step_next = step;
        int gg = to[numb][i];
        if(gg == -1) return ;
        step_next += gg;
        dfs(state | g , i , step_next);
    }
}
int main() {
    scanf("%d%d%d" , &n , &m , &k);
    for(int i = 0 ; i < n ; i++) {
        scanf("%s" , mmp[i]);
    }
    int sta = 0;
    memset(to , 0 , sizeof(to));
    for(int i = 0 ; i < k ; i++) {
        scanf("%d%d" , &point[i].x , &point[i].y);
        if(mmp[point[i].x][point[i].y] == '1') sta = -1;
    }
    point[k].x = 0 , point[k].y = 0;
    point[k + 1].x = n - 1 , point[k + 1].y = m - 1;
    for(int i = 0 ; i <= k + 1 ; i++) {
        for(int j = 0 ; j <= k + 1 ; j++) {
            if(i == j) continue;
            TnT sta , ed;
            sta.x = point[i].x , sta.y = point[i].y;
            ed.x = point[j].x , ed.y = point[j].y;
            to[i][j] = bfs(sta , ed);
            to[j][i] = to[i][j];
        }
    }
    if(mmp[n - 1][m - 1] == '1') sta = -1;
    ans = -1;
    dfs(sta , k , 0);
    printf("%d
" , ans);
    return 0;
}