#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char str[100][100];
int v[100][100];
int n,m;
int vv[100];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(str[x][y]=='!')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(temp>res)
res=temp;
return;
}
int i;
double re=temp;
for(i=0;i<4;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int f=0;
if(str[nx][ny]>='A'&&str[nx][ny]<='G'&&!vv[str[nx][ny]-'A'])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
f=1;
vv[str[nx][ny]-'A']=1;
temp*=(1- ( (double)p[str[nx][ny]-'A']/100 ));
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
v[nx][ny]=1;
dfs(nx,ny);
if(f==1)
vv[str[nx][ny]-'A']=0;
v[nx][ny]=0;
temp=re;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
class ColorfulMazeTwo
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
public:
double getProbability(vector <string> maze, vector <int> trap)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int sx,sy;
int i,j;
for(i=0;i<7;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
p[i]=trap[i];
}
n=maze.size();
m=maze[0].length();
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j=0;j<m;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
str[i][j]=maze[i][j];
if(str[i][j]=='$')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{sx=i;sy=j;}
}
}
v[sx][sy]=1;
dfs(sx,sy);
return res;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
};
vector<string> maze;
vector<int>trap;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
原来这个题最多只有7个字母可以改变概率,所以只要统计到达终点后,经过几个字母即可,可以用二进制来表示。
这个v[x][y][mark],当经过x,y点,并且使用过mark二进制所代表的字符集时,为1.
总状态数为50*50*256,总算不超时了,呵呵。
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char str[100][100];
int v[51][51][1<<8];
int n,m;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dir[4][2]=
{
{0,1},
{1,0},
{0,-1},
{-1,0}};
int p[100];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double res=0;
double temp=1;
void dfs(int x,int y,int mark)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(v[x][y][mark])return ;
v[x][y][mark]=1;
int i;
for(i=0;i<4;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(str[nx][ny]>='A'&&str[nx][ny]<='G')
dfs(nx,ny,nm|=( 1<<(str[nx][ny]-'A') ) );
else
dfs(nx,ny,nm);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
class ColorfulMazeTwo
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
public:
double getProbability(vector <string> maze, vector <int> trap)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int sx,sy;
int ex,ey;
int i,j;
for(i=0;i<7;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
p[i]=trap[i];
}
n=maze.size();
m=maze[0].length();
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j=0;j<m;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
str[i][j]=maze[i][j];
if(str[i][j]=='$')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{sx=i;sy=j;}
if(str[i][j]=='!')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ex=i;ey=j;}
}
}
double ans=0;
dfs(sx,sy,0);
for(i=0;i<(1<<7);i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
double res=1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(v[ex][ey][i])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(j=0;j<7;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(i&(1<<j))
res*=(1-p[j]/100.0);
}
if(res>ans)
ans=res;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
return ans;
}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
vector<string> maze;
vector<int>trap;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)