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<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#define N 810
#define INF 2147483647
using 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;
};
queue<Node>Q;
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<4;i++){
u=x+dx[i]; v=y+dy[i];
if(!b[u][v]&&a[u][v]&&dep<k&&u>=1&&u<=n&&v>=1&&v<=m){
b[x][y]=1;
Q.push((Node){u,v,dep+1});
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
while((ch=getchar())!='#'&&ch!='.'&&ch!='S');
if(ch=='.')a[i][j]=1;
else if(ch=='S'){
a[i][j]=1;
sx=i; sy=j;
}
}
}
if(sx==1||sx==n||sy==1||sy==m){
printf("0\n");
return 0;
}
ans=INF;
Q.push((Node){sx,sy,0});
Bfs();
printf("%d\n",ans+1);
}
