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[ << ];

int to[][] , dr[][] = { ,  , - ,  ,  ,  ,  , -};

char mmp[][];

int n , m , k;

struct TnT {

    int x , y , step;

}point[];

bool vis[][];

int bfs(TnT sta , TnT ed) {

    queue<TnT>q;

    memset(vis , false , sizeof(vis));

    sta.step = ;

    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 =  ; i <  ; i++) {

            TnT gl = gg;

            gl.x += dr[i][];

            gl.y += dr[i][];

            gl.step++;

            if(gl.x >=  && gl.x < n && gl.y >=  && gl.y < m && mmp[gl.x][gl.y] != '' && !vis[gl.x][gl.y]) {

                vis[gl.x][gl.y] = true;

                q.push(gl);

            }

        }

    }

    return -;

}

int ans;

void dfs(int state , int numb , int step) {

    if(state == -) return ;

    TnT sta , ed;

    sta = point[numb];

    if(state == ( << k) - ) {

        ed = point[k + ];

        if(to[numb][k + ] == -) return ;

        if(ans == -) {

            ans = step + to[numb][k + ];

        }

        else ans = min(ans , step + to[numb][k + ]);

        return ;

    }

    for(int i =  ; i < k ; i++) {

        int g = ( << i);

        if(state & g) continue;

        TnT ed = point[i];

        int step_next = step;

        int gg = to[numb][i];

        if(gg == -) return ;

        step_next += gg;

        dfs(state | g , i , step_next);

    }

}

int main() {

    scanf("%d%d%d" , &n , &m , &k);

    for(int i =  ; i < n ; i++) {

        scanf("%s" , mmp[i]);

    }

    int sta = ;

    memset(to ,  , sizeof(to));

    for(int i =  ; i < k ; i++) {

        scanf("%d%d" , &point[i].x , &point[i].y);

        if(mmp[point[i].x][point[i].y] == '') sta = -;

    }

    point[k].x =  , point[k].y = ;

    point[k + ].x = n -  , point[k + ].y = m - ;

    for(int i =  ; i <= k +  ; i++) {

        for(int j =  ; j <= k +  ; 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 - ][m - ] == '') sta = -;

    ans = -;

    dfs(sta , k , );

    printf("%d\n" , ans);

    return ;

}