题解 P2489 【[SDOI2011]迷宫探险】
**这道题的数据太水了！！强烈建议管理加强数据！！
传奇英雄，精心制造Hack数据
https://www.luogu.com.cn/discuss/show/231577
以上数据可以卡掉部分洛谷和new_BZOJ（vijos）的题解。
有2种错误的解法：有人用dp[a][b][c][d]表示在(a,b)的位置，状态为c，血量为d，但是可能会遇见环的情况，导致用没有算完的状态更新了答案。（详见上面hack的那个帖子）
还有人加了一维fa，记录这个点是从哪来的。但是仍然会被卡。
那么，我们发现这道题的关键在于如何避免产生环。
本人思路：首先，我们算出当前状态可以到达那些未知或有毒的陷阱。
然后只考虑向未知或有毒的陷阱转移。
这样子，显然是没有环的。（因为向有毒的陷阱会掉1滴血，向未知的陷阱会知道未知陷阱的信息，而这样显然是不可逆的）
我们将到达终点/掉血/未知陷阱作为“一步”，而不是将一次上下左右作为“一步”
因为到达空地/已知无毒陷阱是“平淡无奇”的，没有意义，我们认为能够直接越过，不考虑。
然后，我们就愉快地A掉了这个题！
所以说，大家一定要严谨治学啊！不要以为A掉了就对了，要多加思考。
最后，祝大家省选愉快！（距离进省队还有2天）
BJ/HE/SC稳住！天佑CCF，天佑我中华！
//作者：传奇英雄
#include<bits/stdc++.h>
using namespace std;
const int g=32,g2=245,s[6]={1,3,9,27,81,243},x[4]={1,-1},y[4]={0,0,1,-1};
int m,n,k,h,sx,sy,u[g2],w,id,state,mark[g][g],m1,m2,m3;
double dp[g][g][g2][6],p[g2][6];
bool vis[g][g][g2][6],f[6],v2[g][g][g2];
char ch[g][g];
vector< pair<int,int> > v[g][g][g2];
int get(int t,int a)
{
if(u[t]>=0) return u[t];
for(int i=a;;i++)
if(!(t/s[i]%3))//考虑2种情况，未知的为0或为1
return u[t]=get(t+s[i],i+1)+get(t+(s[i]<<1),i+1);
}
void dfs2(int a,int b)
{
for(int i=0;i<4;i++)
{
m1=a+x[i],m2=b+y[i];
if(m1&&m1<=m&&m2&&m2<=n&&mark[m1][m2]!=id)
{
mark[m1][m2]=id;//打上标记，不走重复的点
if(ch[m1][m2]=='.'||ch[m1][m2]=='$')//空地
dfs2(m1,m2);
else
{
if(ch[m1][m2]=='@')//目标
{
for(int j=1;j<=h;j++)
{
vis[a][b][state][j]=vis[sx][sy][state][j]=1;
dp[a][b][state][j]=dp[sx][sy][state][j]=1;
}
return;
}
m3=int(ch[m1][m2])-65;//陷阱
if(m3>=0&&m3<k)
{
if(state/s[m3]%3==1)//无毒
dfs2(m1,m2);
else
v[sx][sy][state].push_back(make_pair(m1,m2));//有毒
}
}
}
if(vis[sx][sy][state][1])//已经到达终点
{
for(int j=1;j<=h;j++)
{
vis[a][b][state][j]=1;
dp[a][b][state][j]=1;
}
return;
}
}
}
double dfs(int a,int b,int c,int d)
{
if(vis[a][b][c][d])
return dp[a][b][c][d];
if(!v2[a][b][c])//当前状态没有被计算过
{
v2[a][b][c]=1;//标记已经计算过了，不重复计算
sx=a,sy=b,state=c;//记录当前状态
mark[a][b]=++id;//标记已经经过的位置，用id标记，省了清空
dfs2(a,b);//计算当前状态中能到达的有毒或未知陷阱
if(vis[a][b][c][d]) return 1;//已经到达目标
}
vis[a][b][c][d]=1;
double ans=0;
for(int i=0;i<v[a][b][c].size();i++)
{
int m4=v[a][b][c][i].first;
int m5=v[a][b][c][i].second;//陷阱的坐标
int m6=int(ch[m4][m5])-65;//陷阱的类型
if(c/s[m6]%3)//有毒陷阱
{
if(d>1)//必须血量大于1才能进有毒陷阱
ans=max(ans,dfs(m4,m5,c,d-1));
}
else//未知的陷阱
if(d==1)//只有1滴血时只能进无毒的陷阱
ans=max(ans,dfs(m4,m5,c+s[m6],d)*p[c][m6]);
else//无毒或有毒
ans=max(ans,dfs(m4,m5,c+s[m6],d)*p[c][m6]+dfs(m4,m5,c+(s[m6]<<1),d-1)*(1-p[c][m6]));
if(ans==1) return dp[a][b][c][d]=1;
}
return dp[a][b][c][d]=ans;
}
int main()
{
//freopen("in","r",stdin);
scanf("%d%d%d%d\n",&m,&n,&k,&h);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%c",&ch[i][j]);
if(ch[i][j]=='$')
sx=i,sy=j;//起点的位置
}
scanf("\n");//注意坑人的回车
}
memset(u,-1,sizeof(u));
w=(s[k]-1)>>1;
while(w<s[k])//我们定的状态，0未知，1无毒，2有毒
{
scanf("%d",&u[w]);
w++;
for(int i=0;;i++)//将输入的编号转化为状态
if(f[i])
{
f[i]=0;
w+=s[i];
}
else
{
f[i]=1;
break;
}
}
for(int i=0;i<s[k];i+=3)//末位为1或2的显然已经不用考虑，因为计算i-1的时候已经算过了，i-1最后1位加1
get(i,0);//计算未知的所有可能之和
for(int i=0;i<s[k];i++)
for(int j=0;j<k;j++)
if(!(i/s[j]%3))
p[i][j]=u[i+s[j]]*1.0/(u[i+s[j]]+u[i+(s[j]<<1)]);//计算概率
printf("%.3f",dfs(sx,sy,0,h));
return 0;
}
本题思路来自chdy大佬。他的代码也是对的。感谢大佬！
不建议删掉错误的题解。因为错误的题解确实也是一种很好的思路。（建议各位大佬学习一下错误的题解，然后认真思考一下为什么错了）做走迷宫问题的时候一定要注意环的问题。