HDU 1983 Kaitou Kid – The Phantom Thief (2)

神题，搜索太差，来自网络的题解与程序

思路：
       封锁出口或者入口周围的格子.
最多需要4个封锁点.
所以我们可以采取这样的策略:
1.寻找一条盗贼的可行路线,如果没有,返回0.
2.计算封锁出口和入口四周需要的封锁点数量,取小的一个,假设是k,k <=4
3.从少到多,遍历所有封锁点个数小于k的方案,验证是否是一条有效的覆盖方案
                  (可以通过是否阻止了1中的盗贼线路进行快速验证).
                  如果有有效覆盖方案,返回这个方案的覆盖点值,否则继续.
4.如果没有比k小的覆盖方案,返回k.
时间复杂度:
最多(M*N)^3次有效覆盖验证.即(8*8)^3=256k次.其中有很大一部分可以通过快速验证排除(取决于1的路径长短,所以一般1应该求出最短路径的可行路线)

#include<queue>
#include<iostream>
#include<algorithm>
#define FOR(i,n) for(i=0;i<n;i++)  using namespace std;  char Map[][][];//地图
char vis[][][];//访问记录
int sx,sy,n,m,t;
int dir[][]={{,},{-,},{,},{,-}};//下，上，右，左   struct Node{
    int x,y,f;//坐标,楼层
};  bool bfs(){//标准的BFS
    queue<Node>que;
    Node no,ne;
    int i;
    memset(vis,-,sizeof(vis));
    no.x=sx,no.y=sy,no.f=;
    que.push(no);
    vis[][sx][sy]=;
    while(!que.empty()){
        no=que.front(),que.pop();
        if(vis[no.f][no.x][no.y]>=t) continue;//算是剪枝吧
        FOR(i,){
            ne.x=no.x+dir[i][],ne.y=no.y+dir[i][],ne.f=no.f;
            if(ne.x<||ne.y<||ne.x>=n||ne.y>=m) continue;
            if(Map[ne.f][ne.x][ne.y]=='#') continue;
            if(Map[ne.f][ne.x][ne.y]=='J') ne.f=;
            if(Map[ne.f][ne.x][ne.y]=='E'&&ne.f) return false;//ne.f=1表示已经拿到J
            if(vis[ne.f][ne.x][ne.y]!=-) continue;
            vis[ne.f][ne.x][ne.y]=vis[no.f][no.x][no.y]+;
            que.push(ne);
        }
    }
    return true;
}  bool DFS(int tot){//标准DFS ,tot表示要堵的点的个数
    int i,j;
    if(!tot) return bfs();
    FOR(i,n)
    FOR(j,m){
        if(Map[][i][j]=='.'||Map[][i][j]=='J'){
            char emp=Map[][i][j];
            Map[][i][j]='#';
            if(DFS(tot-)) return true;
            Map[][i][j]=emp;
        }
    }
    return false;
}  int main(){
    int k,i,j,a,b;
    scanf("%d",&k);
    while(k--){
        scanf("%d%d%d",&n,&m,&t);
        FOR(i,n){
            scanf("%s",Map[][i]);
            FOR(j,m) if(Map[][i][j]=='S') sx=i,sy=j;
            strcpy(Map[][i],Map[][i]);//复制第二层楼
        }
        FOR(i,)  if(DFS(i)){//把0~3个的点搜索一遍
            printf("%d\n",i);
            break;
        }
        i==?puts(""):;//如果前三点都没有成立的，最多四个，所以输出四
    }
    return ;
}