3 条题解
-
2
//水题一道 #include<bits/stdc++.h> #define MAXN 25 #define p 100007 #define int long long using namespace std; int n,m,K,now,pre; char c[MAXN][MAXN]; int head[p+3],nxt[1<<24]; int f[2][1<<24],fst[2][3][1<<24]; int cnt[2]; void insert(int state1,int state2,int state3,int val) { int ha=((((1ll*state1<<16)|state2)<<4)|state3)%p+1;//哈希 for(int i=head[ha];i;i=nxt[i]) if(fst[now][0][i]==state1&&fst[now][1][i]==state2&&fst[now][2][i]==state3) { f[now][i]=max(f[now][i],val); return; } f[now][++cnt[now]]=val; fst[now][0][cnt[now]]=state1; fst[now][1][cnt[now]]=state2; fst[now][2][cnt[now]]=state3;//三个状态 nxt[cnt[now]]=head[ha]; head[ha]=cnt[now]; }//hash表 int left(int state,int pos,int val) {//向左寻找左括号 int tot=1; while(true) { int pl=(state>>(pos<<1))&3; if(pl==2)tot++;if(pl==1) tot--; if(!tot)return state^(pl<<(pos<<1))^(val<<(pos<<1)); pos--; } } int right(int state,int pos,int val) {//向右寻找右括号 int tot=1; while(true) { int pl=(state>>(pos<<1))&3; if(pl==1)tot++;if(pl==2) tot--; if(!tot)return state^(pl<<(pos<<1))^(val<<(pos<<1)); pos++; } } char tmp[MAXN][MAXN]; signed main() { scanf("%lld%lld%lld",&n,&m,&K); for(int i=0;i<n;i++)scanf("%s",c[i]); if(n<m) {//n<m的时候把地图转90度 memcpy(tmp,c,sizeof(c)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) c[j][i]=tmp[i][j]; swap(n,m); } cnt[0]=1; for(int i=0;i<n;i++) { for(int j=1;j<=cnt[now];j++) fst[now][0][j]<<=2; for(int j=1;j<=cnt[now];j++) fst[now][1][j]=(fst[now][1][j]^(((fst[now][1][j]>>(m+1<<1))&3)<<(m+1<<1)))<<2;//更新上一行的状态 for(int j=0;j<m;j++) { pre=now;now^=1;cnt[now]=0; memset(head,0,sizeof(head));//注意初始化 for(int k=1;k<=cnt[pre];k++) { int sta=fst[pre][0][k],stb=fst[pre][1][k],stc=fst[pre][2][k]; int val=f[pre][k]; if(sta>=(1<<(m+1<<1)))continue; int pl1=(sta>>(j<<1))&3;//right int pl2=(sta>>(j+1<<1))&3;//down int r=(stb>>(j<<1))&3;//右状态 int ur=(stb>>(j+1<<1))&3;//右上状态 int u=(stb>>(j+2<<1))&3;//上状态 int ul=(stb>>(j+3<<1))&3;//左上状态 int now=(sta^(pl1<<(j<<1))^(pl2<<(j+1<<1))); if((!pl1&&r==1)||(!pl2&&u==1))//1 { if(pl1||pl2)continue; insert(now,stb^(ur<<(j+1<<1)),stc,val);//放障碍 if(stc<K&&c[i][j]=='.') insert(now,stb^(ur<<(j+1<<1))^(3<<(j+1<<1)),stc+1,val+(r==1)+(ur==1)+(u==1)+(ul==1));//放炮台 } else if(c[i][j]=='#'){if(!pl1&&!pl2)insert(now,stb^(ur<<(j+1<<1)),stc,val);}//2 else if(c[i][j]=='.')//3 { if(!pl1&&!pl2)//1) { if(stc<K) insert(now,stb^(ur<<(j+1<<1))^(3<<(j+1<<1)),stc+1, val+(r==1)+(ur==1)+(u==1)+(ul==1));//放炮台 insert(now^(1<<(j<<1))^(2<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3));//走 insert(now,stb^(ur<<(j+1<<1)),stc,val);//不走 } else if(!pl1&&pl2)//2） { insert(now^(pl2<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); insert(now^(pl2<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } else if(pl1&&!pl2)//2） { insert(now^(pl1<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); insert(now^(pl1<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } else if(pl1==1&&pl2==1)//3） insert(right(now,j,1),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==2&&pl2==2)//4） insert(left(now,j,2),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==2&&pl2==1)//6） insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==1&&pl2==3)//7） insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==2&&pl2==3)//8） insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==3&&pl2==1)//7） insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==3&&pl2==2)//8） insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==3&&pl2==3)//9） insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } else if(c[i][j]=='S'||c[i][j]=='T')//4 { if(c[i][j]=='S'&&!pl1&&!pl2)//1） { insert(now^(3<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); insert(now^(3<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } else if(c[i][j]=='T'&&!pl1&&!pl2)//1） { insert(now^(3<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); insert(now^(3<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } else if(!pl1&&pl2==1)//2） insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(!pl1&&pl2==2)//3） insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==1&&!pl2)//2） insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==2&&!pl2)//3） insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==3&&!pl2)//4） insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(!pl1&&pl2==3)//4） insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } } } } int ans=0; for(int i=1;i<=cnt[now];i++)//统计答案 if(!fst[now][0][i]) ans=max(ans,f[now][i]); printf("%lld",ans); return 0; } -
2
#include<bits/stdc++.h> #define MAXN 25 #define p 100007 #define int long long using namespace std; int n,m,K,now,pre; char c[MAXN][MAXN]; int head[p+3],nxt[1<<24]; int f[2][1<<24],fst[2][3][1<<24]; int cnt[2]; void insert(int state1,int state2,int state3,int val) { int ha=((((1ll*state1<<16)|state2)<<4)|state3)%p+1;//哈希 for(int i=head[ha];i;i=nxt[i]) if(fst[now][0][i]==state1&&fst[now][1][i]==state2&&fst[now][2][i]==state3) { f[now][i]=max(f[now][i],val); return; } f[now][++cnt[now]]=val; fst[now][0][cnt[now]]=state1; fst[now][1][cnt[now]]=state2; fst[now][2][cnt[now]]=state3;//三个状态 nxt[cnt[now]]=head[ha]; head[ha]=cnt[now]; }//hash表 int left(int state,int pos,int val) {//向左寻找左括号 int tot=1; while(true) { int pl=(state>>(pos<<1))&3; if(pl==2)tot++;if(pl==1) tot--; if(!tot)return state^(pl<<(pos<<1))^(val<<(pos<<1)); pos--; } } int right(int state,int pos,int val) {//向右寻找右括号 int tot=1; while(true) { int pl=(state>>(pos<<1))&3; if(pl==1)tot++;if(pl==2) tot--; if(!tot)return state^(pl<<(pos<<1))^(val<<(pos<<1)); pos++; } } char tmp[MAXN][MAXN]; signed main() { scanf("%lld%lld%lld",&n,&m,&K); for(int i=0;i<n;i++)scanf("%s",c[i]); if(n<m) {//n<m的时候把地图转90度 memcpy(tmp,c,sizeof(c)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) c[j][i]=tmp[i][j]; swap(n,m); } cnt[0]=1; for(int i=0;i<n;i++) { for(int j=1;j<=cnt[now];j++) fst[now][0][j]<<=2; for(int j=1;j<=cnt[now];j++) fst[now][1][j]=(fst[now][1][j]^(((fst[now][1][j]>>(m+1<<1))&3)<<(m+1<<1)))<<2;//更新上一行的状态 for(int j=0;j<m;j++) { pre=now;now^=1;cnt[now]=0; memset(head,0,sizeof(head));//注意初始化 for(int k=1;k<=cnt[pre];k++) { int sta=fst[pre][0][k],stb=fst[pre][1][k],stc=fst[pre][2][k]; int val=f[pre][k]; if(sta>=(1<<(m+1<<1)))continue; int pl1=(sta>>(j<<1))&3;//right int pl2=(sta>>(j+1<<1))&3;//down int r=(stb>>(j<<1))&3;//右状态 int ur=(stb>>(j+1<<1))&3;//右上状态 int u=(stb>>(j+2<<1))&3;//上状态 int ul=(stb>>(j+3<<1))&3;//左上状态 int now=(sta^(pl1<<(j<<1))^(pl2<<(j+1<<1))); if((!pl1&&r==1)||(!pl2&&u==1))//1 { if(pl1||pl2)continue; insert(now,stb^(ur<<(j+1<<1)),stc,val);//放障碍 if(stc<K&&c[i][j]=='.') insert(now,stb^(ur<<(j+1<<1))^(3<<(j+1<<1)),stc+1,val+(r==1)+(ur==1)+(u==1)+(ul==1));//放炮台 } else if(c[i][j]=='#'){if(!pl1&&!pl2)insert(now,stb^(ur<<(j+1<<1)),stc,val);}//2 else if(c[i][j]=='.')//3 { if(!pl1&&!pl2)//1) { if(stc<K) insert(now,stb^(ur<<(j+1<<1))^(3<<(j+1<<1)),stc+1, val+(r==1)+(ur==1)+(u==1)+(ul==1));//放炮台 insert(now^(1<<(j<<1))^(2<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3));//走 insert(now,stb^(ur<<(j+1<<1)),stc,val);//不走 } else if(!pl1&&pl2)//2） { insert(now^(pl2<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); insert(now^(pl2<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } else if(pl1&&!pl2)//2） { insert(now^(pl1<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); insert(now^(pl1<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } else if(pl1==1&&pl2==1)//3） insert(right(now,j,1),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==2&&pl2==2)//4） insert(left(now,j,2),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==2&&pl2==1)//6） insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==1&&pl2==3)//7） insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==2&&pl2==3)//8） insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==3&&pl2==1)//7） insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==3&&pl2==2)//8） insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==3&&pl2==3)//9） insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } else if(c[i][j]=='S'||c[i][j]=='T')//4 { if(c[i][j]=='S'&&!pl1&&!pl2)//1） { insert(now^(3<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); insert(now^(3<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } else if(c[i][j]=='T'&&!pl1&&!pl2)//1） { insert(now^(3<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); insert(now^(3<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } else if(!pl1&&pl2==1)//2） insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(!pl1&&pl2==2)//3） insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==1&&!pl2)//2） insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==2&&!pl2)//3） insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(pl1==3&&!pl2)//4） insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); else if(!pl1&&pl2==3)//4） insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc, val+(r==3)+(ur==3)+(u==3)+(ul==3)); } } } } int ans=0; for(int i=1;i<=cnt[now];i++)//统计答案 if(!fst[now][0][i]) ans=max(ans,f[now][i]); printf("%lld",ans); return 0; } -
1
📝 题目大意
给定一个 的网格，其中
S为起点，T为终点，#为原有障碍。 你可以放置无限个额外障碍以及至多 个炮塔。 胖头鱼星人会从S到T选择一条受伤害最小的路径前进。如果途中遇到障碍或炮塔，则不能经过该格子。 炮塔会攻击其周围的 8 个方向（即 8 连通相邻格子）。每当星人走到炮塔的攻击范围内，就会受到 1 点伤害。 你的任务是合理布置障碍和炮塔，在保证至少存在一条从S到T的路径的前提下，使得星人到达目的地所受的最小伤害最大化。💡 解题思路
-
核心转化： 既然我们可以放置无限个障碍，那么为了让星人受到的伤害最大，最暴力的策略就是用障碍把其他所有的路都堵死，只留下唯一的一条从
S到T的路径。 因为路只有一条，星人没得选，只能走我们为他铺好的这条路。因此，原问题等价转化为：在网格中寻找一条从S到T的简单路径，并放置至多 个炮塔（炮塔和路径不可重合，均需避开原有障碍#），使得该路径受到的总伤害最大化。 而路径受到的总伤害，实质上就是所有 8 连通相邻的（路径格子, 炮塔）对的数量。 -
状态压缩 DP（轮廓线 / 插头 DP）： 题目保证 ，非常适合基于轮廓线的插头 DP。当 时，我们可以直接将网格转置，从而始终保证轮廓线宽度不超过 6。 逐行逐列扫描网格时，当前格子 可以设定为以下三种类型（
cur_type）：0：障碍（不可通行区域）。1：路径（星人走的简单路径，S和T处必须为1）。2：炮塔（防御塔，总数限制为 ）。
-
状态设计（32 位整数完美压缩）： 要保证只有一条合法路径并计算 8 连通伤害，处理格子 时需要记录：
P（插头状态）：长度为 ，每个元素表示轮廓线上的插头情况。取值为0（无插头）、1（左括号）、2（右括号）、3（已连通起点S或终点T的端点独立插头）。占用 个 bit。B（方块类型状态）：长度为 。取值为0,1,2，记录当前轮廓线上已填好的格子类型，专用于判断 8 连通。占用 个 bit。stc（已放炮塔数）：最高 15，占用 4 个 bit。 总共只需要 bit，刚好打包进一个uint32_t。
-
伤害计算与 B 数组的妙用： 当轮廓线推到 时，
B数组精确地保留了左、左上、上、右上四个邻居的历史选择结果：- 若 填
1（路径），只要它的四个邻居中有2（炮塔），每个2都会产生 1 点伤害。 - 若 填
2（炮塔），只要它的四个邻居中有1（路径），每个1都会产生 1 点伤害。 因为我们是从左到右、从上到下遍历，这种“只往后看一半方向”的检查可以刚好不重不漏地覆盖全部的 8 连通对！
- 若 填
-
插头连通性转移：
- 端点格 (
S或T)：必须填1，且消耗或生成端点。若新生成则设为插头3；若吸收已有的1或2，则通过括号匹配逻辑将其对应的另一端转化为插头3。 - 普通格填
1：应用标准插头 DP 的转移规律。如果是两个3插头相遇，则表示完成了整条从S到T的连接！ - 填
0或2：该处不能有插头，因此要求上方和左侧均无插头流入。
- 端点格 (
⏱️ 复杂度分析
- 时间复杂度：，其中 是任意单步中的合法状态数量。因为网格非常窄且连通性限制严格，绝大部分无效状态会被剪枝， 最大仅在数千左右。整体耗时极低（通常十几毫秒跑完）。
- 空间复杂度：由于采用滚动哈希表，只需维护两层的状态，大小均设为 ，空间消耗约为几 MB，属于 级别，非常充裕。
💻 标准代码 (C++)
#include <cstdint> #include <iostream> #include <vector> #include <string> #include <cstring> #include <algorithm> using namespace std; const int MOD = 500009; struct HashMap { int head[MOD]; int nxt[1000000]; uint32_t key[1000000]; int val[1000000]; int size; void init() { memset(head, -1, sizeof(head)); size = 0; } void clear() { for (int i = 0; i < size; ++i) { head[key[i] % MOD] = -1; } size = 0; } void insert(uint32_t k, int v) { int h = k % MOD; for (int i = head[h]; i != -1; i = nxt[i]) { if (key[i] == k) { if (v > val[i]) val[i] = v; return; } } key[size] = k; val[size] = v; nxt[size] = head[h]; head[h] = size++; } } HM[2]; int n, m, K; char grid[25][25]; inline void decode(uint32_t state, int* P) { for (int i = 0; i <= m; ++i) P[i] = (state >> (i * 2)) & 3; } inline uint32_t encode(int* P) { uint32_t state = 0; for (int i = 0; i <= m; ++i) state |= (P[i] << (i * 2)); return state; } int find_match_1(int* P, int pos) { int tot = 1; for (int i = pos - 1; i >= 0; --i) { if (P[i] == 2) tot++; else if (P[i] == 1) tot--; if (tot == 0) return i; } return -1; } int find_match_2(int* P, int pos) { int tot = 1; for (int i = pos + 1; i <= m; ++i) { if (P[i] == 1) tot++; else if (P[i] == 2) tot--; if (tot == 0) return i; } return -1; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); if (!(cin >> n >> m >> K)) return 0; for (int i = 0; i < n; ++i) { cin >> grid[i]; } // 保证轮廓线宽度不超过 6 if (n < m) { char tmp[25][25]; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) tmp[j][i] = grid[i][j]; swap(n, m); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { grid[i][j] = tmp[i][j]; } } } HM[0].init(); HM[1].init(); int now = 0; HM[now].insert(0, 0); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { HM[now ^ 1].clear(); for (int idx = 0; idx < HM[now].size; ++idx) { uint32_t k = HM[now].key[idx]; int v = HM[now].val[idx]; int P[8], B[8]; decode(k & 0x3FFF, P); decode((k >> 14) & 0x3FFF, B); int stc = k >> 28; int p1 = P[j], p2 = P[j + 1]; int c_left = (j == 0) ? 0 : B[j - 1]; int c_tl = (j == 0) ? 0 : B[j]; int c_top = B[j + 1]; int c_tr = (j == m - 1) ? 0 : B[j + 2]; auto push_state = [&](int* nP, int* nB, int n_stc, int damage) { if (j == m - 1 && nP[m] != 0) return; if (i == n - 1 && nP[j] != 0) return; uint32_t nk = encode(nP) | (encode(nB) << 14) | (n_stc << 28); HM[now ^ 1].insert(nk, v + damage); }; for (int cur_type = 0; cur_type <= 2; ++cur_type) { if (grid[i][j] == '#' && cur_type != 0) continue; if ((grid[i][j] == 'S' || grid[i][j] == 'T') && cur_type != 1) continue; if (cur_type == 2 && stc >= K) continue; int damage = 0; if (cur_type == 1) damage = (c_left == 2) + (c_tl == 2) + (c_top == 2) + (c_tr == 2); else if (cur_type == 2) damage = (c_left == 1) + (c_tl == 1) + (c_top == 1) + (c_tr == 1); int nP[8], nB[8]; memcpy(nP, P, sizeof(nP)); memcpy(nB, B, sizeof(nB)); nB[j] = cur_type; int n_stc = stc + (cur_type == 2 ? 1 : 0); if (cur_type != 1) { if (p1 == 0 && p2 == 0) { nP[j] = 0; nP[j + 1] = 0; push_state(nP, nB, n_stc, damage); } } else { if (grid[i][j] == 'S' || grid[i][j] == 'T') { if (p1 == 0 && p2 == 0) { nP[j] = 0; nP[j + 1] = 3; push_state(nP, nB, n_stc, damage); nP[j] = 3; nP[j + 1] = 0; push_state(nP, nB, n_stc, damage); } else if (p1 != 0 && p2 == 0) { nP[j] = 0; nP[j + 1] = 0; if (p1 == 1) nP[find_match_2(P, j)] = 3; else if (p1 == 2) nP[find_match_1(P, j)] = 3; push_state(nP, nB, n_stc, damage); } else if (p1 == 0 && p2 != 0) { nP[j] = 0; nP[j + 1] = 0; if (p2 == 1) nP[find_match_2(P, j + 1)] = 3; else if (p2 == 2) nP[find_match_1(P, j + 1)] = 3; push_state(nP, nB, n_stc, damage); } } else { if (p1 == 0 && p2 == 0) { nP[j] = 1; nP[j + 1] = 2; push_state(nP, nB, n_stc, damage); } else if (p1 == 0 && p2 != 0) { nP[j] = 0; nP[j + 1] = p2; push_state(nP, nB, n_stc, damage); nP[j] = p2; nP[j + 1] = 0; push_state(nP, nB, n_stc, damage); } else if (p1 != 0 && p2 == 0) { nP[j] = 0; nP[j + 1] = p1; push_state(nP, nB, n_stc, damage); nP[j] = p1; nP[j + 1] = 0; push_state(nP, nB, n_stc, damage); } else if (p1 == 1 && p2 == 1) { nP[j] = 0; nP[j + 1] = 0; nP[find_match_2(P, j + 1)] = 1; push_state(nP, nB, n_stc, damage); } else if (p1 == 2 && p2 == 2) { nP[j] = 0; nP[j + 1] = 0; nP[find_match_1(P, j)] = 2; push_state(nP, nB, n_stc, damage); } else if (p1 == 2 && p2 == 1) { nP[j] = 0; nP[j + 1] = 0; push_state(nP, nB, n_stc, damage); } else if (p1 == 3 && p2 == 1) { nP[j] = 0; nP[j + 1] = 0; nP[find_match_2(P, j + 1)] = 3; push_state(nP, nB, n_stc, damage); } else if (p1 == 1 && p2 == 3) { nP[j] = 0; nP[j + 1] = 0; nP[find_match_2(P, j)] = 3; push_state(nP, nB, n_stc, damage); } else if (p1 == 3 && p2 == 2) { nP[j] = 0; nP[j + 1] = 0; nP[find_match_1(P, j + 1)] = 3; push_state(nP, nB, n_stc, damage); } else if (p1 == 2 && p2 == 3) { nP[j] = 0; nP[j + 1] = 0; nP[find_match_1(P, j)] = 3; push_state(nP, nB, n_stc, damage); } else if (p1 == 3 && p2 == 3) { nP[j] = 0; nP[j + 1] = 0; push_state(nP, nB, n_stc, damage); } } } } } now ^= 1; } HM[now ^ 1].clear(); for (int idx = 0; idx < HM[now].size; ++idx) { uint32_t k = HM[now].key[idx]; int v = HM[now].val[idx]; int P[8], B[8]; decode(k & 0x3FFF, P); decode((k >> 14) & 0x3FFF, B); int stc = k >> 28; for (int ki = m; ki >= 1; --ki) P[ki] = P[ki - 1]; P[0] = 0; for (int ki = m; ki >= 1; --ki) B[ki] = B[ki - 1]; B[0] = 0; uint32_t nk = encode(P) | (encode(B) << 14) | (stc << 28); HM[now ^ 1].insert(nk, v); } now ^= 1; } int ans = 0; for (int i = 0; i < HM[now].size; ++i) { if ((HM[now].key[i] & 0x3FFF) == 0) { ans = max(ans, HM[now].val[i]); } } cout << ans << "\n"; return 0; } -
liukainuoKN
@ 2026-6-27 20:46:23
- 1