#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
char str[100][100];
int v[100][100];
int n,m;
int vv[100];
int dir[4][2]=
{{0,1},{1,0},{0,-1},{-1,0}};
int p[100];
double res=0;
double temp=1;
void dfs(int x,int y)
{
if(str[x][y]=='!')
{
if(temp>res)
res=temp;
return;
}
int i;
double re=temp;
for(i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(str[nx][ny]!='#'&&nx<n&&nx>=0&&ny<m&&ny>=0&&!v[nx][ny])
{
int f=0;
if(str[nx][ny]>='A'&&str[nx][ny]<='G'&&!vv[str[nx][ny]-'A'])
{
f=1;
vv[str[nx][ny]-'A']=1;
temp*=(1- ( (double)p[str[nx][ny]-'A']/100 ));
}
v[nx][ny]=1;
dfs(nx,ny);
if(f==1)
vv[str[nx][ny]-'A']=0;
v[nx][ny]=0;
temp=re;
}
}
}
class ColorfulMazeTwo
{
public:
double getProbability(vector <string> maze, vector <int> trap)
{
int sx,sy;
int i,j;
for(i=0;i<7;i++)
{
p[i]=trap[i];
}
n=maze.size();
m=maze[0].length();
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
str[i][j]=maze[i][j];
if(str[i][j]=='$')
{sx=i;sy=j;}
}
}
v[sx][sy]=1;
dfs(sx,sy);
return res;
}
};
vector<string> maze;
vector<int>trap;
int main()
{
ColorfulMazeTwo t;
maze.push_back(".$.");
maze.push_back("A#B");
maze.push_back("A#B");
maze.push_back(".!.");
trap.push_back(50);
trap.push_back(40);
trap.push_back(0);
trap.push_back(0);
trap.push_back(0);
trap.push_back(0);
trap.push_back(0);
t.getProbability(maze,trap);
printf("%lf\n",res);
}
原來這個(gè)題最多只有7個(gè)字母可以改變概率，所以只要統(tǒng)計(jì)到達(dá)終點(diǎn)后，經(jīng)過幾個(gè)字母即可，可以用二進(jìn)制來表示。
這個(gè)v[x][y][mark]，當(dāng)經(jīng)過x,y點(diǎn)，并且使用過mark二進(jìn)制所代表的字符集時(shí)，為1.
總狀態(tài)數(shù)為50*50*256，總算不超時(shí)了,呵呵。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
char str[100][100];
int v[51][51][1<<8];
int n,m;
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int p[100];
double res=0;
double temp=1;
void dfs(int x,int y,int mark)
{
if(v[x][y][mark])return ;
v[x][y][mark]=1;
int i;
for(i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
int nm=mark;
if(str[nx][ny]!='#'&&nx<n&&nx>=0&&ny<m&&ny>=0)
{
if(str[nx][ny]>='A'&&str[nx][ny]<='G')
dfs(nx,ny,nm|=( 1<<(str[nx][ny]-'A') ) );
else
dfs(nx,ny,nm);
}
}
}
class ColorfulMazeTwo
{
public:
double getProbability(vector <string> maze, vector <int> trap)
{
int sx,sy;
int ex,ey;
int i,j;
for(i=0;i<7;i++)
{
p[i]=trap[i];
}
n=maze.size();
m=maze[0].length();
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
str[i][j]=maze[i][j];
if(str[i][j]=='$')
{sx=i;sy=j;}
if(str[i][j]=='!')
{ex=i;ey=j;}
}
}
double ans=0;
dfs(sx,sy,0);
for(i=0;i<(1<<7);i++)
{
double res=1;
if(v[ex][ey][i])
{
for(j=0;j<7;j++)
{
if(i&(1<<j))
res*=(1-p[j]/100.0);
}
if(res>ans)
ans=res;
}
}
return ans;
}
};
vector<string> maze;
vector<int>trap;
int main()
{
ColorfulMazeTwo t;
maze.push_back(".$.");
maze.push_back("A#B");
maze.push_back("A#B");
maze.push_back(".!.");
trap.push_back(50);
trap.push_back(40);
trap.push_back(0);
trap.push_back(0);
trap.push_back(0);
trap.push_back(0);
trap.push_back(0);
t.getProbability(maze,trap);
printf("%lf\n",res);
}