UVA-1601
The Morning after Halloween（UVA-1601）
Problem:https://vjudge.net/problem/UVA-1601
Input:
5 5 2
#####
#A#B#
# #
#b#a#
#####
16 4 3
################
## ########## ##
# ABCcba #
################
16 16 3
################
### ## # ##
## # ## # c#
# ## ########b#
# ## # # # #
# # ## # # ##
## a# # # # #
### ## #### ## #
## # # # #
# ##### # ## ##
#### #B# # #
## C# # ###
# # # ####### #
# ###### A## #
# # ##
################
0 0 0
Output:
7
36
77
Solution:
双向bfs经典题，这题的核心算法就是双向bfs，但是对于本题的优化是非常有趣的。在题中提出了没个2*2的方块里至少一个墙壁，所以可通行的地方最多有75%的方格，如果我们直接去搜图中的点，那么每个点需要检验五个状态，同时又有三个鬼，所以要遍历(5^3)种也就是125个，同时有((16 *16)^3)种状态也就是(256^3)种，显然是会超时的，所以有如下优化：
- 我们把每个点的可通行位置提取出来构成一张无向图，在这张图上跑bfs，每次我们只需要遍历可 以到达的点。
- 对所有的空白格编号，搜索针对编号处理。
- 双向bfs搜索，提高搜索效率
- 对每种状态可知，之多有三个鬼分布在图的不同位置，每个数最大为192（图上空白格数，实际会更小），所以应一个三位的192进制数表示即可（整数哈希）。
代码实际写起来会有些不好处理的地方，由于本人较菜，所以代码比较长。大佬可以自行优化orz。
Code：
/**********************************************************
* @Author: Kirito
* @Last Modified by: Kirito
* @Remark:
**********************************************************/
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cout<<#x<<"------"<<x<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;
const int MAXN=31;
const int mv[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int w,h,n;
string str[MAXN];
pii ls[MAXN*MAXN];
int cnt;
vector<int> gp[202];
struct node{
int ad0,ad1,ad2;
int step;
node(int x=0,int y=0,int z=0,int d=1):ad0(x),ad1(y),ad2(z),step(d){}
int getHash(){
return ad0+ad1*256+ad2*256*256;
}
}be,ed;
int vis[8000000],vit[8000000];
int bfs()
{
queue<node> box,que;
if(be.getHash()==ed.getHash()) return 0;
vis[be.getHash()]=1;
vit[ed.getHash()]=1;
box.push(be);que.push(ed);
while(!box.empty()&&!que.empty()){
if(box.size()<que.size()){
int ok=box.front().step;
while(!box.empty()&&ok==box.front().step){
node now=box.front();
box.pop();
for(auto i:gp[now.ad0]){
if(n>1){
for(auto j:gp[now.ad1]){
if(i==j) continue;
if(i==now.ad1&&j==now.ad0) continue;
if(n>2){
for(auto k:gp[now.ad2]){
if(i==k||j==k) continue;
if(i==now.ad2&&k==now.ad0) continue;
if(j==now.ad2&&k==now.ad1) continue;
node nxt=node(i,j,k,now.step+1);
int hh=nxt.getHash();
if(vis[hh]) continue;
if(vit[hh]){
return nxt.step+vit[hh]-2;
}
vis[hh]=nxt.step;
box.push(nxt);
}
}
else{
node nxt=node(i,j,0,now.step+1);
int hh=nxt.getHash();
if(vis[hh]) continue;
if(vit[hh]){
return nxt.step+vit[hh]-2;
}
vis[hh]=nxt.step;
box.push(nxt);
}
}
}
else{
node nxt=node(i,0,0,now.step+1);
int hh=nxt.getHash();
if(vis[hh]) continue;
if(vit[hh]){
return nxt.step+vit[hh]-2;
}
vis[hh]=nxt.step;
box.push(nxt);
}
}
}
}
else{
int ok=que.front().step;
while(!que.empty()&&ok==que.front().step){
node now=que.front();
que.pop();
for(auto i:gp[now.ad0]){
if(n>1){
for(auto j:gp[now.ad1]){
if(i==j) continue;
if(i==now.ad1&&j==now.ad0) continue;
if(n>2){
for(auto k:gp[now.ad2]){
if(i==k||j==k) continue;
if(i==now.ad2&&k==now.ad0) continue;
if(j==now.ad2&&k==now.ad1) continue;
node nxt=node(i,j,k,now.step+1);
int hh=nxt.getHash();
if(vit[hh]) continue;
if(vis[hh]){
return nxt.step+vis[hh]-2;
}
vit[hh]=nxt.step;
que.push(nxt);
}
}
else{
node nxt=node(i,j,0,now.step+1);
int hh=nxt.getHash();
if(vit[hh]) continue;
if(vis[hh]){
return nxt.step+vis[hh]-2;
}
vit[hh]=nxt.step;
que.push(nxt);
}
}
}
else{
node nxt=node(i,0,0,now.step+1);
int hh=nxt.getHash();
if(vit[hh]) continue;
if(vis[hh]){
return nxt.step+vis[hh]-2;
}
vit[hh]=nxt.step;
que.push(nxt);
}
}
}
}
}
return -1;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
#endif
while(cin>>w>>h>>n){
if(w==0&&h==0&&n==0) break;
cin.get();
for(int i=0;i<h;i++){
getline(cin,str[i]);
}
cnt=0;
be=node();ed=node();
ls[cnt++]=make_pair(0,0);
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(str[i][j]!='#'){
ls[cnt++]=make_pair(i,j);
}
}
}
sort(ls,ls+cnt);
for(int i=0;i<200;i++)
gp[i].clear();
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(str[i][j]!='#'){
int u=int(lower_bound(ls,ls+cnt,make_pair(i,j))-ls);
if(str[i][j]>='A'&&str[i][j]<='Z'){
int m=int(str[i][j]-'A');
if(m==0) ed.ad0=u;
else if(m==1) ed.ad1=u;
else ed.ad2=u;
}
if(str[i][j]>='a'&&str[i][j]<='z'){
int m=int(str[i][j]-'a');
if(m==0) be.ad0=u;
else if(m==1) be.ad1=u;
else be.ad2=u;
}
gp[u].push_back(u);
for(int k=0;k<4;k++){
int nx=i+mv[k][0];
int ny=j+mv[k][1];
if(nx>=0&&nx<h&&ny>=0&&ny<w&&str[nx][ny]!='#'){
int v=int(lower_bound(ls,ls+cnt,make_pair(nx,ny))-ls);
gp[u].push_back(v);
}
}
}
}
}
CSE(vis,0);CSE(vit,0);
cout<<bfs()<<endl;
}
return 0;
}
我这份代码跑了560ms，算是比较快的了