| 记录编号 |
87151 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
疯狂火箭 |
最终得分 |
100 |
| 用户昵称 |
 cstdio |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.760 s |
| 提交时间 |
2014-02-01 15:46:07 |
内存使用 |
0.70 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const ll HASHVAL=50021;
//N代表行数,M代表列数
const int SIZEN=15;
int N=9,M=6;
//本题中下标从1开始
int matchpos;//点着火柴的位置
char board[SIZEN][SIZEN]={0};
int plug_rot[10][10][10]={0};//第i种插头(从1到4)的4种旋转状态
//12345分别是L,-,T,+,空
//上左下右是1234
void print2dig(ll s){//调试接口,输出s的所有二进制位
for(int i=0;i<N+1;i++){cout<<((s>>i)&1)<<" ";}
}
void print16dig(ll s){//调试接口,输出s的所有十六进制位
for(int i=0;i<N+1;i++){cout<<((s>>(i<<2))&15)<<" ";}
}
class HASHSET{//一个不允许重复元素的哈希表
public:
int hash[HASHVAL];//哈希表,储存在状态vector中的下标
vector<ll> st;//状态
void clear(void){
memset(hash,-1,sizeof(hash));
st.clear();
}
void insert(ll s){//向表中添加一个元素,若有重复则无视之
int hashpos=s%HASHVAL;
while(hash[hashpos]!=-1){
if(st[hash[hashpos]]==s) return;
hashpos++;
if(hashpos==HASHVAL) hashpos=0;
}
hash[hashpos]=st.size();
st.push_back(s);
}
};
//状态码的格式是:前10个bit是十个插头的点燃状态,后40个bit(即10个16进制数)是十个插头的最小表示法
//点燃状态和最小表示法,均按从低位到高位依次存储从上到下的状态(即x从1到10)
class STATE{
public:
bool fired[SIZEN];//是否被点燃
int comp[SIZEN];//最小表示法表示的连通状态
int ncomp;//连通块数量
void print(void){//调试接口,输出当前的点燃和连通状态
cout<<"点燃状态: ";
for(int i=1;i<=N+1;i++){cout<<fired[i]<<" ";}cout<<endl;
cout<<"连通块数量: "<<ncomp<<endl;
cout<<"最小表示法: ";
for(int i=1;i<=N+1;i++){cout<<comp[i]<<" ";}cout<<endl;
}
void clear(void){
ncomp=0;
memset(fired,0,sizeof(fired));
memset(comp,0,sizeof(comp));
}
void merge(int a,int b){//将连通块a,b合并
//这里是将编号为b的都标为编号a
int comfir=0;//如果连通块之一点亮,那么两个连通块都将被点亮
for(int i=1;i<=N+1;i++){//连通块里的点燃状态应该是相同的
if(comp[i]==a){
comfir=comfir|fired[i];
break;
}
}
for(int i=1;i<=N+1;i++){
if(comp[i]==b){
comfir=comfir|fired[i];
break;
}
}
for(int i=1;i<=N+1;i++){
if(comp[i]==a) fired[i]=fired[i]|comfir;
else if(comp[i]==b) fired[i]=fired[i]|comfir,comp[i]=a;
}
}
void relabel(void){//重新标号,并重新计算连通块数量
ncomp=0;
int atp[SIZEN]={0};
memset(atp,0,sizeof(atp));
for(int i=1;i<=N+1;i++){
if(comp[i]>0&&atp[comp[i]]==0){
atp[comp[i]]=++ncomp;
}
comp[i]=atp[comp[i]];
}
}
void demdl(ll s){//将s中的信息解调
clear();
ll fs,cs;//点燃状态和连通状态
cs=(s&(((ll)1<<40)-1));
fs=(s>>40)&((1<<10)-1);
for(int i=0;i<N+1;i++){
fired[i+1]=((fs>>i)&1);
comp[i+1]=((cs>>(i<<2))&15);
ncomp=max(ncomp,comp[i+1]);//由于是最小表示法,因此最大的连通块编号就是连通块数量
}
}
ll mdl(void){//将s中的信息调制在一个整数中
ll fs=0,cs=0;
for(int i=N;i>=0;i--){
fs=(fs<<1)+fired[i+1];
cs=(cs<<4)+comp[i+1];
}
return cs+(fs<<40);
}
};
void nextline(HASHSET &nowf){
vector<ll> temp=nowf.st;
nowf.clear();
for(int i=0;i<temp.size();i++){
ll s,fs,cs;//fs是点燃信息,cs是连通状态
s=temp[i];
cs=(s&(((ll)1<<40)-1));
fs=(s>>40)&((1<<10)-1);
cs<<=4;cs&=(((ll)1<<40)-1);
fs<<=1;fs&=((1<<10)-1);
nowf.insert(cs+(fs<<40));
}
}
bool better(STATE &a,STATE &b){//a是否绝对优于b
for(int i=1;i<=N+1;i++){
if(b.comp[i]&&!a.comp[i]) return false;//b中有这个插头,a中没有
if(b.fired[i]>a.fired[i]) return false;//b中点燃了,a中没有
}
return true;
}
int numburn(ll s){//统计状态s能发射多少火箭
ll fs=(s>>40)&((1<<10)-1);
int ans=0;
for(int i=0;i<N+1;i++){
if((fs>>i)&1) ans++;
}
return ans;
}
int maxburn;
STATE bestst;
ll numstate=0;
void getrot(void){
plug_rot[1][1][1]=plug_rot[1][1][2]=1;//L型
plug_rot[2][1][2]=plug_rot[2][1][4]=1;//-型
plug_rot[3][1][2]=plug_rot[3][1][3]=plug_rot[3][1][4]=1;//T型
plug_rot[4][1][1]=plug_rot[4][1][2]=plug_rot[4][1][3]=plug_rot[4][1][4]=1;//+型
for(int i=1;i<=5;i++){
for(int j=1;j<4;j++){
for(int k=1;k<4;k++){
plug_rot[i][j+1][k+1]=plug_rot[i][j][k];
}
plug_rot[i][j+1][1]=plug_rot[i][j][4];
}
}
}
void update(HASHSET &nowf,int x,int y,ll nows){//向哈希表S中,对格子(x,y)更新上一个是nows
//上一个,即状态为nows的格子是(x-1,y)
int tubetype;
if(board[x][y]=='L') tubetype=1;
else if(board[x][y]=='-') tubetype=2;
else if(board[x][y]=='T') tubetype=3;
else if(board[x][y]=='+') tubetype=4;
else if(board[x][y]=='.') tubetype=5;
STATE S;
S.demdl(nows);
for(int i=1;i<=4;i++){
if(tubetype==5&&i>1) continue;//空格子只有一种旋转情况
if(tubetype==4&&i>1) continue;//十字形格子也只有一种旋转情况
if(tubetype==2&&i>2) continue;//一字型格子有两种旋转情况
//L型和T型都有四种旋转情况
int xycom=S.ncomp+1,xyfir=0;//这个格子的连通块编号/是否被点燃,初始时是一个单独的连通分量,并且未被点燃
int *plugcon=plug_rot[tubetype][i];//当前这种旋转状态的四方向插头存在情况
STATE T=S;
for(int j=1;j<=2;j++){//只有上插头和左插头会与之前的发生联系
if(plugcon[j]&&S.comp[x-1+j]){//如果这两个插头都存在,线就连在了一块
xyfir|=S.fired[x-1+j];
T.merge(S.comp[x-1+j],xycom);//把xycom合并到原有的连通块显然更省
xycom=S.comp[x-1+j];
}
}
if(!plugcon[4]) T.fired[x]=0,T.comp[x]=0;
else T.fired[x]=xyfir,T.comp[x]=xycom;//这是右插头的状态
if(!plugcon[3]) T.fired[x+1]=0,T.comp[x+1]=0;
else T.fired[x+1]=xyfir,T.comp[x+1]=xycom;//这是下插头的状态
T.relabel();
//剪枝一:
bool hasfir=0;
for(int j=1;j<=N+1;j++) hasfir=hasfir||T.fired[j];
if(!hasfir) continue;
//剪枝二:
int cnum[SIZEN]={0};
for(int j=1;j<=N+1;j++) cnum[T.comp[j]]++;
for(int j=1;j<x;j++) if(!T.fired[j]&&cnum[T.comp[j]]==1) T.comp[j]=0;
//剪枝三:
ll Tcode=T.mdl();
int temp=numburn(Tcode);
if(temp>maxburn){
maxburn=temp;
bestst=T;
}
else if(better(bestst,T)) continue;
nowf.insert(Tcode);
}
}
HASHSET f[2];
void work(void){
int k=0;
f[k].clear();
STATE S;
S.clear();
S.fired[matchpos+1]=true,S.comp[matchpos+1]=1;//仅有一个被点燃的插头
S.ncomp=1;
f[k].insert(S.mdl());
for(int j=1;j<=M;j++){
for(int i=1;i<=N;i++){
numstate+=f[k].st.size();//这里统计了扩展出的状态总数
f[k^1].clear();
maxburn=0;
for(int km=0;km<f[k].st.size();km++){
update(f[k^1],i,j,f[k].st[km]);
}
k^=1;
}
nextline(f[k]);
}
int ans=0;
for(int i=0;i<f[k].st.size();i++) ans=max(ans,numburn(f[k].st[i]));
printf("%d\n",ans);
}
bool read(void){
if(scanf("%d",&matchpos)==EOF) return false;
for(int i=1;i<=N;i++) scanf("%s",&board[i][1]);
return true;
}
int main(){
freopen("rocketmania.in","r",stdin);
freopen("rocketmania.out","w",stdout);
getrot();
read();
work();
//cout<<clock()<<endl;
//下面是多组数据的程序
//while(read()) work();
//下面是计时的程序
/*int st=0;
while(read()){
numstate=0;
work();
int nt=clock();
cout<<"t:"<<nt-st<<endl;
st=nt;
cout<<"numstate:"<<numstate<<endl;
}*/
return 0;
}