PKJ1138 - c21coterie @ ウィキ

北京大学掲載のプログラムの練習問題。

問題No1038を解く。

動的計画法にBit演算まで動員して解いたのだけど速度が出なかった、コード実行速度下位ランクという結果に。

２重再帰の深さ優先探索で良かったのだろうか？

しかしそれだと縦に入れる横に入れるの分岐で組み合わせ数が凄いことになりそうなのだけど？？？

 

 

#include<stdio.h>

#include<map>

#include<string.h>

 

//グローバル変数まとめ

int map[153];//1bit一マスで盤面を表す

const int okBlock=0;

const int badBlock=1;

int n,m,k;

//まとめ終わり

 

void lineCalc(int row,int col,int count,int kekka,std::map<int,int>& next){

//一列だけ走査していく

if(row==m){

kekka=kekka>>m;//一行分削除する

if(next.find(kekka)==next.end()){

next[kekka]=count;//初めてのパタン

}else if(next[kekka]<count){

next[kekka]=count;//より大きいパタンが見つかった

}

return ;

}

//今のマスが不良品かチップで埋まっているなら

if((kekka>>(row-1))&1){

lineCalc(row+1,col,count,kekka,next);

return;

}

//このマスに何も入れない

lineCalc(row+1,col,count,kekka,next);

 

//横を入れれるかチェックする

int chip=3<<(row-1);

int col0=kekka&chip;

int col1=kekka&(chip<<m);

int col2=kekka&(chip<<(m*2));

if(col0==0 && col1==0 && col2==0){

lineCalc(row+1,col,count+1,kekka|chip|(chip<<m)|(chip<<(m*2)),next);//横を入れた

}

if(row>=m-1)return;//縦を入れれないマスに到達。

chip=7<<(row-1);

col0=kekka&chip;

col1=kekka&(chip<<m);

//縦を入れれるかチェックする

if(col0==0 && col1==0){

lineCalc(row+1,col,count+1,kekka|chip|(chip<<m),next);//縦を入れた

}

}

 

 

void setData(){

//一行ずつ動的計画法で計算していく。

memset(map,okBlock,sizeof(map));

int x,y;

scanf("%d %d %d",&n,&m,&k);

while(k--){

scanf("%d %d",&x,&y);

map[x]|=badBlock<<(y-1);//1bit一マスで一列ずつ升目を格納する。

}

map[n+1]=~((int)0);//番兵

std::map<int,int> memo,next;//

std::map<int,int>::iterator it;

memo[0]=0;

for(int col=1;col<n;col++){

next.clear();

int badLines=map[col]|(map[col+1]<<m)|(map[col+2]<<(2*m));//邪魔なブロックを記録する

 

for(it=memo.begin();it!=memo.end();it++){

lineCalc(1,col,(*it).second,(*it).first|badLines,next);//今のラインで動的計画法を試す

}

memo.clear();

memo.insert(next.begin(),next.end());

}

int ans=0;

for(it=memo.begin();it!=memo.end();it++){

if(ans==0||(*it).second>ans){

ans=(*it).second;

}

}

printf("%d\n",ans);

}

 

int main(){

int d;

scanf("%d",&d);

while(d--){

setData();

}

}