Problem 787: 密室逃脱 Time Limit: 2000 ms Memory Limit: 524288 KB
Problem Description 小J被关在密室里！
密室的构造是一个H×W的棋盘，即有H行W列，第i行第j列的房间用Ai,j 表示。
若Ai,j =’#’，则该房间的门是锁上的；
若Ai,j =’.’，则该房间是可以自由进出的；
小J被困在Ai,j =’S’的地方，该房间是可以自由进出的。
房间是四相邻的，即(i,j)可以移动到(i+1,j),(i-1,j),(i,j-1),(i,j+1)
小J将通过如下方式逃脱密室，每一回合，她会按顺序执行如下操作：
移动至多K 次，可以不移动，此时被锁着的房间是不能够进入的 选择至多K个锁着的房间打开，可以不选择任何房间，从此那些房间将一直可以自由进出。 出口在密室的四周，即第1行，第1列，第H行，第W列的所有房间，出口一开始可能是被锁住的。
你需要用最少的回合移动到出口，输出这个回合数。
数据范围和子任务：
3≦H≦800
3≦W≦800
1≦K≦H×W
Ai,j 是 ‘#’ ‘.’ ‘S’ 中的一种，有且仅有一个Ai,j 为S
Subtask1（30分）：H≦4,W≦4；
Subtask2（10分）：不存在Ai,j =#
Subtask3（10分）：不存在Ai,j =.
Subtask4（50分）：无特殊限制
Input 第一行读入三个整数H,W,K
接下来H行，每行W个字符，表示Ai,j。
Output 输出一行一个数，表示小J最少要用多少回合逃出密室。
Sample Input 【样例输入1】
3 3 3#.##S.###【样例输入2】
3 3 3####S####【样例输入3】
7 7 2################...#####S#####.#.#####.##########Sample Output 【样例输出1】
1
【样例输出2】
2
【样例输出3】
2
【样例解释】
对于样例1：
小J可以在一个回合内移动到（1，2）
对于样例2：
小J第一个回合不能移动，但她解锁了房间（1，2），然后她在第二个回合移动到（1，2）逃离密室。
Problem Source dhr
题解一开始理解错题意 题意:
小J将通过如下方式逃脱密室，每一回合，她会按顺序执行如下操作：移动至多K 次，可以不移动，此时被锁着的房间是不能够进入的选择至多K个锁着的房间打开，可以不选择任何房间，从此那些房间将一直可以自由进出。说明一个回合中可以有两种操作 一个回合走的k次可以由前一回合解锁 所以路径对答案没有影响 所以走直线到边界最优
我们先走k次(一回合) 用这一回合走的点更新答案 可以用bfs实现 时间O(n*m)
比赛时看出是搜索题 以为要走奇奇怪怪的路线 找不到结论就做其他题去了 没能签到 有点亏啊
参考文献[1]AtCoder Grand Contest 014做题记录 [2]cs的比赛总结
ac代码 #include#include#include#include#include#define N 810#define INF 2147483647using namespace std;int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0},n,m,k,ans,sx,sy,num,u,v;bool a[N][N],b[N][N];char ch;struct Node{int x,y,dep;};queueQ;void Bfs(){int x,y,dep;while(!Q.empty()){x=Q.front().x; y=Q.front().y; dep=Q.front().dep; Q.pop();if(x==1||x==n||y==1||y==m){ans=0;return;}num=min(min(n-x,m-y),min(x-1,y-1));num=(num-1)/k+1;ans=min(ans,num);for(int i=0;i