The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

TC 464 DIV 2 1000 穷搜所有状态

 

   #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);
}



原来这个题最多只有7个字母可以改变概率,所以只要统计到达终点后,经过几个字母即可,可以用二进制来表示。
这个v[x][y][mark],当经过x,y点,并且使用过mark二进制所代表的字符集时,为1.
总状态数为50*50*256,总算不超时了,呵呵。


#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);
}


 

posted on 2010-03-17 01:14 abilitytao 阅读(1192) 评论(1)  编辑 收藏 引用

评论

# re: TC 464 DIV 2 1000 穷搜所有状态 2010-03-19 12:09 罗莱家纺专卖店

圣诞节方法方法商店  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理