神题，搜索太差，来自网络的题解与程序
思路：
封锁出口或者入口周围的格子.
最多需要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[2][10][10];//地图 char vis[2][10][10];//访问记录 int sx,sy,n,m,t; int dir[][2]={{1,0},{-1,0},{0,1},{0,-1}};//下，上，右，左 struct Node{ int x,y,f;//坐标,楼层 }; bool bfs(){//标准的BFS queue<Node>que; Node no,ne; int i; memset(vis,-1,sizeof(vis)); no.x=sx,no.y=sy,no.f=0; que.push(no); vis[0][sx][sy]=0; while(!que.empty()){ no=que.front(),que.pop(); if(vis[no.f][no.x][no.y]>=t) continue;//算是剪枝吧 FOR(i,4){ ne.x=no.x+dir[i][0],ne.y=no.y+dir[i][1],ne.f=no.f; if(ne.x<0||ne.y<0||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=1; 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]!=-1) continue; vis[ne.f][ne.x][ne.y]=vis[no.f][no.x][no.y]+1; 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[0][i][j]=='.'||Map[0][i][j]=='J'){ char emp=Map[0][i][j]; Map[0][i][j]='#'; if(DFS(tot-1)) return true; Map[0][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[0][i]); FOR(j,m) if(Map[0][i][j]=='S') sx=i,sy=j; strcpy(Map[1][i],Map[0][i]);//复制第二层楼 } FOR(i,4) if(DFS(i)){//把0~3个的点搜索一遍 printf("%d ",i); break; } i==4?puts("4"):0;//如果前三点都没有成立的，最多四个，所以输出四 } return 0; }