| 记录编号 |
88638 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[UVa 1094] 修筑水道 |
最终得分 |
100 |
| 用户昵称 |
 cstdio |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.361 s |
| 提交时间 |
2014-02-22 21:08:02 |
内存使用 |
18.45 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<vector>
using namespace std;
//本题下标从0开始
typedef long long ll;
const int SIZEN=20,SIZEM=9,HASHVAL=13131;
int N,M;//行数和列数
int opt[SIZEN][SIZEM][HASHVAL]={0};
int pre[SIZEN][SIZEM][HASHVAL]={0};
char board[SIZEN][SIZEM]={0};
class HASHMAP{
public:
int hash[HASHVAL];
vector<pair<ll,int> > st;
void clear(void){
memset(hash,-1,sizeof(hash));
st.clear();
}
void insert(int x,int y,int op,int last,ll s,int f){
if(st.size()>=HASHVAL){cout<<"hash overflow!"<<endl;}
int hashpos=s%HASHVAL;
while(hash[hashpos]!=-1){
if(st[hash[hashpos]].first==s){
if(st[hash[hashpos]].second<f){
st[hash[hashpos]].second=f;
opt[x][y][hash[hashpos]]=op;
pre[x][y][hash[hashpos]]=last;
}
return;
}
hashpos++;
if(hashpos==HASHVAL) hashpos=0;
}
hash[hashpos]=st.size();
opt[x][y][st.size()]=op;
pre[x][y][st.size()]=last;
st.push_back(make_pair(s,f));
}
};
HASHMAP F[2];
class STATE{
public:
int plug[SIZEM+1];//储存轮廓线上诸插头
bool exist[SIZEM+1];//储存轮廓线及左上诸格是否挖通
void clear(void){memset(plug,0,sizeof(plug));memset(exist,0,sizeof(exist));}
ll mdl(void){//调制
ll ans=0;
for(int i=M;i>=0;i--) ans=(ans<<1)+exist[i];
for(int i=M;i>=0;i--) ans=(ans<<2)+plug[i];
return ans;
}
void demdl(ll s){//解调
for(int i=0;i<=M;i++) plug[i]=s&3,s>>=2;
for(int i=0;i<=M;i++) exist[i]=s&1,s>>=1;
}
void nextline(void){//从这一行的末尾变到下一行的开头
for(int i=M-1;i>=0;i--) plug[i+1]=plug[i],exist[i+1]=exist[i];
plug[0]=exist[0]=0;
}
};
int rightmatch(STATE &s,int k){//与s的第k位匹配的右插头
int dta=1,temp;
while(k<=M){
k++;
temp=s.plug[k];
if(temp==1) dta++;
else if(temp==2) dta--;
if(dta==0) return k;
}
cout<<"bracket match error!"<<endl;
return -1;
}
int leftmatch(STATE &s,int k){
int dta=-1,temp;
while(k>=0){
k--;
temp=s.plug[k];
if(temp==1) dta++;
else if(temp==2) dta--;
if(dta==0) return k;
}
cout<<"bracket match error!"<<endl;
return -1;
}
void changeblock(STATE &s,int y,int exi,int d,int r){//列数为y,exi为存在与否,d是下,r是右
if(!exi){
s.plug[y]=s.plug[y+1]=0;
s.exist[y]=0;
}
else{
s.plug[y]=d,s.plug[y+1]=r;
s.exist[y]=1;
}
}
void changematch(STATE &s,int y,int t){//把和插头y匹配的插头改成t
if(s.plug[y]==1){
s.plug[rightmatch(s,y)]=t;
}
else s.plug[leftmatch(s,y)]=t;
}
bool plug_exi(int x,int y,int dir){//2下4右
if(dir==2&&x==N-1){
if(y==M-1) return true;//右下角认为是向下挖了
return false;
}
if(dir==4&&y==M-1) return false;
return true;
}
void update(int k,int x,int y){//用F[k]去更新F[k^1],新增的一格是(x,y)
F[k^1].clear();
STATE S,T;
int nowf,l,lu,u,ru,p,q;
for(int i=0;i<F[k].st.size();i++){
S.clear();
S.demdl(F[k].st[i].first);
if(y==0) S.nextline();
nowf=F[k].st[i].second;
//左:y-1,左上:y,上:y+1,右上:y+2
l=y>0?S.exist[y-1]:0;
lu=S.exist[y];
u=S.exist[y+1];
ru=y<M-1?S.exist[y+2]:0;
p=S.plug[y],q=S.plug[y+1];//左插头和上插头
if(p==0&&q==0){//什么都不放
T=S;
changeblock(T,y,0,0,0);
F[k^1].insert(x,y,0,i,T.mdl(),nowf);
}
if(board[x][y]=='.'){//这里讨论放的
if(p==0&&q==0){//新建连通分量
if(!lu&&!u&&!l&&plug_exi(x,y,2)&&plug_exi(x,y,4)){
T=S;
changeblock(T,y,1,1,2);
F[k^1].insert(x,y,1,i,T.mdl(),nowf+1);
}
}
else if(p==0&&q>0){//上插头的延伸
if(!l&&plug_exi(x,y,2)){
T=S;
changeblock(T,y,1,q,0);
F[k^1].insert(x,y,1,i,T.mdl(),nowf+1);
}
if(!ru&&!l&&plug_exi(x,y,4)){
T=S;
changeblock(T,y,1,0,q);
F[k^1].insert(x,y,1,i,T.mdl(),nowf+1);
}
}
else if(p>0&&q==0){//左插头的延伸
if(!u&&!ru&&plug_exi(x,y,2)){
T=S;
changeblock(T,y,1,p,0);
F[k^1].insert(x,y,1,i,T.mdl(),nowf+1);
}
if(!u&&plug_exi(x,y,4)){
T=S;
changeblock(T,y,1,0,p);
F[k^1].insert(x,y,1,i,T.mdl(),nowf+1);
}
}
else if(p==1&&q==1){
if(!lu){
T=S;
changematch(T,y+1,1);//将上插头对应的2改成1
changeblock(T,y,1,0,0);
F[k^1].insert(x,y,1,i,T.mdl(),nowf+1);
}
}
else if(p==2&&q==2){
if(!lu){
T=S;
changematch(T,y,2);//将左插头对应的1改成2
changeblock(T,y,1,0,0);
F[k^1].insert(x,y,1,i,T.mdl(),nowf+1);
}
}
else if(p==2&&q==1){
if(!lu){
T=S;
changeblock(T,y,1,0,0);
F[k^1].insert(x,y,1,i,T.mdl(),nowf+1);
}
}
if(p==2&&q==3){
if(!lu){
T=S;
changematch(T,y,3);//将左插头对应的1改成3
changeblock(T,y,1,0,0);
F[k^1].insert(x,y,1,i,T.mdl(),nowf+1);
}
}
if(p==3&&q==1){
if(!lu){
T=S;
changematch(T,y+1,3);//将上插头对应的2改成3
changeblock(T,y,1,0,0);
F[k^1].insert(x,y,1,i,T.mdl(),nowf+1);
}
}
}
}
}
bool legal_end(ll s){//状态s是否是合法的终点
//若合法,则只有一个独立插头,即M-1号
ll plug=s&((1<<(2*(M+1)))-1);
return plug==(3<<(2*(M-1)));
}
void work(void){
int k=0;
STATE start;
F[k].clear();
start.clear();
start.exist[0]=1;//第一个格子
start.plug[0]=3;//第一个格子向下伸出独立插头
F[k].insert(0,0,1,-1,start.mdl(),1);
start.plug[0]=0,start.plug[1]=3;//第一个格子向右伸出独立插头
F[k].insert(0,0,1,-1,start.mdl(),1);
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(!i&&!j) continue;
update(k,i,j);
k^=1;
}
}
int ans=0,ansid=0;
for(int i=0;i<F[k].st.size();i++){
if(legal_end(F[k].st[i].first)&&F[k].st[i].second>ans){
ans=F[k].st[i].second;
ansid=i;
}
}
char ansgrid[SIZEN][SIZEM]={0};
memcpy(ansgrid,board,sizeof(board));
int step;
for(int i=N-1;i>=0;i--){
for(int j=M-1;j>=0;j--){
step=opt[i][j][ansid];
if(step) ansgrid[i][j]='C';
ansid=pre[i][j][ansid];
}
}
cout<<ans<<endl;
/*for(int i=0;i<N;i++){
for(int j=0;j<M;j++) cout<<ansgrid[i][j];
cout<<endl;
}
cout<<endl;*/
}
int kase=0;
bool read(void){
memset(board,0,sizeof(board));
memset(opt,0,sizeof(opt));
memset(pre,0,sizeof(pre));
scanf("%d%d",&N,&M);
if(!N&&!M) return false;
printf("Case %d:\n",++kase);
string str;
for(int i=0;i<N;i++){
cin>>str;
for(int j=0;j<M;j++) board[i][j]=str[j];
}
return true;
}
int main(){
freopen("channel.in","r",stdin);
freopen("channel.out","w",stdout);
while(read()) work();
return 0;
}