【HDU】1693 Eat the Trees
4754 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=1693
題意：n×mのボードは簡単な回路（複数可）でボード全体を覆う方案を求めて、障害格は放置してはいけません。（n，m<=11）
冗談ですよね。ああ、ああ。裸のプラグdp………
私はhashを呼び出している間にセットの価値を忘れてしまいました。
1 h調整しましたね。ああ、あ………
そして本題は前の問題を適当に変えたらいいです。
題意：n×mのボードは簡単な回路（複数可）でボード全体を覆う方案を求めて、障害格は放置してはいけません。（n，m<=11）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
struct H {
static const int M=1000007;
struct E { int next, to; }e[M<<1];
int ihead, cnt, hash[M];
ll sum[M];
H() { ihead=cnt=0; memset(hash, -1, sizeof hash); memset(sum, 0, sizeof sum); }
bool find(int x, int &pos) {
pos=x%M;
while(1) { if(hash[pos]==x) return false; if(hash[pos]==-1) break; ++pos; if(pos==M) pos=0; }
hash[pos]=x; return true;
}
void ins(int a, ll b) {
int pos; if(!find(a, pos)) { sum[pos]+=b; return; }
e[++cnt].next=ihead; ihead=cnt; e[cnt].to=pos; sum[pos]=b;
}
void clr() { for(int i=ihead; i; i=e[i].next) hash[e[i].to]=-1, sum[e[i].to]=0; ihead=cnt=0; }
}T1, T2;
#define BIT(a,b) ((a)<<((b)<<1))
#define CLR(a,b) (a^=((a)&BIT(3,b)))
#define GET(a,b) (3&((a)>>((b)<<1)))
const int N=11;
int n, m;
ll ans;
bool mp[N][N];
int find(int s, int col, int flag) {
int sum=0;
if(flag) {
for(int i=col; i<=m; ++i) {
int k=GET(s, i);
if(k==1) ++sum;
if(k==2) --sum;
if(!sum) return i;
}
}
else {
for(int i=col; i>=0; --i) {
int k=GET(s, i);
if(k==1) --sum;
if(k==2) ++sum;
if(!sum) return i;
}
}
return -1;
}
void print(int s) {
for(int i=0; i<=m; ++i) { int k=GET(s, i); if(k==0) putchar('#'); else if(k==1) putchar('('); else if(k==2) putchar(')'); }
puts("");
}
#define F puts("error");
bool next(int s, int row, int col, bool U, bool D, bool L, bool R, int &t) {
if((row==n-1&&D) || (row==0&&U) || (col==m-1&&R) || (col==0&&L)) return 0;
if((D&&!mp[row+1][col]) || (R&&!mp[row][col+1])) return 0;
int l=GET(s, col), u=GET(s, col+1), d=0, r=0;
// printf("State:"); print(s);
// printf("row:%d, col:%d, U:%d, D:%d, L:%d, R:%d ", row, col, U, D, L, R);
// printf(" left:"); if(l==1) printf("("); if(l==2) printf(")"); if(l==0) printf("#");
// printf(" uptp:"); if(u==1) printf("("); if(u==2) printf(")"); if(u==0) printf("#"); puts("");
if((l&&!L) || (!l&&L) || (u&&!U) || (!u&&U)) return 0;
t=s; //puts("============
first:"); print(t);
CLR(t, col);
CLR(t, col+1);
if(!l && !u) {
if(R && D) d=1, r=2;
}
else if(l && u) {
if(l==1 && u==1) {
int pos=find(s, col+1, 1);
CLR(t, pos);
t|=BIT(1, pos);
}
else if(l==2 && u==2) {
int pos=find(s, col, 0);
CLR(t, pos);
t|=BIT(2, pos);
}
}
else if(l && !u) {
if(D) d=l, r=0;
if(R) d=0, r=l;
}
else if(!l && u) {
if(D) d=u, r=0;
if(R) d=0, r=u;
}
t|=BIT(d, col);
t|=BIT(r, col+1);
if(col==m-1) t<<=2; //puts("=============
next"); print(t);
return 1;
}
void bfs() {
H *q1, *q2;
q1=&T1; q2=&T2;
q1->clr();
q2->clr();
q1->ins(0, 1);
for(int row=0; row<n; ++row) for(int col=0; col<m; ++col) {
q2->clr(); //printf("q1->cnt:%d
", q1->cnt);
for(int i=q1->ihead; i; i=q1->e[i].next) {
int s=q1->hash[q1->e[i].to], t; //print(s); // ..... hash .... ...
ll sum=q1->sum[q1->e[i].to];
if(!mp[row][col]) { if(next(s, row, col, 0, 0, 0, 0, t)) q2->ins(t, sum); }
else {
if(next(s, row, col, 1, 1, 0, 0, t)) q2->ins(t, sum);
if(next(s, row, col, 1, 0, 1, 0, t)) q2->ins(t, sum);
if(next(s, row, col, 1, 0, 0, 1, t)) q2->ins(t, sum);
if(next(s, row, col, 0, 1, 1, 0, t)) q2->ins(t, sum);
if(next(s, row, col, 0, 1, 0, 1, t)) q2->ins(t, sum);
if(next(s, row, col, 0, 0, 1, 1, t)) q2->ins(t, sum);
}
}
swap(q1, q2);
}
for(int i=q1->ihead; i; i=q1->e[i].next) ans+=q1->sum[q1->e[i].to];
}
int main() {
int cs, temp; scanf("%d", &cs);
for(int cc=1; cc<=cs; ++cc) {
ans=0;
scanf("%d%d", &n, &m);
for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) {
scanf("%d", &temp);
mp[i][j]=temp;
}
bfs();
printf("Case %d: There are %lld ways to eat the trees.
", cc, ans);
}
return 0;
}
冗談ですよね。ああ、ああ。裸のプラグdp………
私はhashを呼び出している間にセットの価値を忘れてしまいました。
1 h調整しましたね。ああ、あ………
そして本題は前の問題を適当に変えたらいいです。