SRM464 div2 hard

拡張幅優先探索って言うのかな。知らないけど。
prob[y][x][visited]でBFSすると通る。
ビット演算で間違えた。

#include <string>
#include <queue>
#include <vector>

using namespace std;

class Q
{
	public:
		int x,y,visited;
		double safe;
};

class ColorfulMazeTwo
{
	public:

		double prob[50][50][(1<<7)];
		
		double getProbability(vector<string> maze,vector<int> trap)
		{
			int h=maze.size(),w=maze[0].size();
			int sx=0,sy=0,ey=0,ex=0;

			for(int i=0;i<h;i++)
				for(int j=0;j<w;j++)
				{
					for(int k=0;k<(1<<7);k++)
						prob[i][j][k]=0.0;
					if(maze[i][j]=='$')
						sy=i,sx=j;
					if(maze[i][j]=='!')
						ey=i,ex=j;
				}

			queue<Q> que;
			Q q;
			q.y=sy,q.x=sx,q.visited=0,q.safe=1.0;
			que.push(q);

			while(!que.empty())
			{
				int x=que.front().x,y=que.front().y,visited=que.front().visited;
				double safe=que.front().safe;
				que.pop();
				
				if(x<0 || w<=x || y<0 || h<=y)
					continue;
				if(maze[y][x]=='#')
					continue;
					
				if('A'<=maze[y][x] && maze[y][x]<='G')
				{
					int m=maze[y][x]-'A';
					if((visited & (1<<m))==0)
					{	
						double d=(double)(100-trap[m])/100.0;
						safe*=d;
						visited = (visited | (1<<m));
					}
				}
				if(prob[y][x][visited] < safe)
				{
					prob[y][x][visited]=safe;

					int mv[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
					for(int i=0;i<4;i++)
					{
						int yy=y+mv[i][0],xx=x+mv[i][1];
						q.y=yy,q.x=xx,q.visited=visited,q.safe=safe;
						que.push(q);
					}
					
					//printf("x=%d y=%d visited=%d safe=%lf\n",x,y,visited,safe);	
				}
			}

			double ans=0.0;
			for(int i=0;i<(1<<7);i++)
				ans=max(ans,prob[ey][ex][i]);
			return ans;
		}
};