Hatena::Grouptopcoder

人生是睡眠 - 夢の中ではredcoder -

 | 

2010-03-18

SRM 464 1000 ColorfulMazeTwo ができねー

15:20

寝過ごした問題をやってみたけど、TLEくらいまくったよパチョレック。

深さ優先探索で全経路を探索するというアホ解答を書いてやったからか・・

(一応現時点での確率が最大値を下回るような場合は枝刈りしたのだが・・)

南無南無・・

下のコードを見てみると、<map>がなぜか書けてない・・タグと解釈されるのか・・

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include 
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
typedef pair<int,int> point;

class ColorfulMazeTwo {
public:
  double res;
  bool visited[50][50];
  int nums[7];
  int m,n;
  vector<string> maze;
  vector<int> trap;

  void dfs(point p,double rate){
	  int i = p.first;
	  int j = p.second;
	  if(rate <= res)
		  return;
	  visited[i][j] = true;
	  char now = maze[i][j];
	  if(now == '#'){
		  visited[i][j] = false;
		  return;
	  }else if(now == '!'){
		  res = max(res,rate);
		  visited[i][j] = false;
		  return;
	  }else if(now >= 'A' && now <= 'G'){
		  nums[now - 'A']++;
		  if(nums[now - 'A'] == 1){
			  rate = rate * (1.0 - trap[now - 'A'] / 100.0);
		  }
	  }

	  if(i + 1 < m && !visited[i+1][j]){
		  dfs(point(i+1,j),rate);
	  }
	  if(i - 1 >= 0 && !visited[i-1][j]){
		  dfs(point(i-1,j),rate);
	  }
	  if(j + 1 < n && !visited[i][j+1]){
		  dfs(point(i,j+1),rate);
	  }
	  if(j - 1 >= 0 && !visited[i][j-1]){
		  dfs(point(i,j-1),rate);
	  }

	  if(now >= 'A' && now <= 'G'){
		  nums[now - 'A']--;
	  }
	  visited[i][j] = false;
  }

  double getProbability(vector <string> _maze, vector <int> _trap) {
    res = 0;
    maze = _maze;
    trap = _trap;
    m = maze.size();
    n = maze[0].size();
    for(int i = 0; i < 7;i++)
    	nums[i] = 0;
    point start;
    double rate = 1;
    for(int i = 0;i < m; i++){
    	for(int j = 0;j < n; j++){
    		visited[i][j] = false;
    		if(maze[i][j] == '$')
    			start = point(i,j);
    	}
    }
    dfs(start,rate);
    return res;
  }
};

DaysiaDaysia2011/07/11 00:01I suppose that sounds and slmels just about right.

jrbheucxwujrbheucxwu2011/07/11 02:35Yu6q5n <a href="http://brsfoujzpmcw.com/">brsfoujzpmcw</a>

qjvtpiiyziqjvtpiiyzi2011/07/11 21:531O1ND0 , [url=http://xqfrihisgflw.com/]xqfrihisgflw[/url], [link=http://lqfhklmuibbp.com/]lqfhklmuibbp[/link], http://wquifuotchbm.com/

xtoigeqxtoigeq2011/07/13 18:45avDUSh <a href="http://nelapwmrzvfp.com/">nelapwmrzvfp</a>

 |