liangdaleo
BAN USERInspired by you all, I think 3-dimensional DP is trival!
double probabilityAliveDP(int x, int y, int N, int step){
if(N==0 || x<0 ||x>=N || y<0 || y>=N ) return 0;
vector<vector<vector<double> > > dp(N+2, vector<vector<double> >(N+2, vector<double>(step+1, 0)));
for(int i=1;i<N+1;i++)
for(int j=1; j<N+1; j++)
dp[i][j][0] = 1.0;
for(int i=1;i<=step;i++){
for(int r = 1; r < N+1; r++){
for(int c = 1; c < N+1; c++){
dp[r][c][i] = 0.25*(dp[r-1][c][i-1]+dp[r+1][c][i-1]+dp[r][c-1][i-1]+dp[r][c+1][i-1]);
}
}
}
return dp[x+1][y+1][step];
}
For the first part:
bool checkLocation(int x, int y, vector<vector<int> >& matrix){
if(x<0 || x>=matrix.size() || y<0 ||y>=matrix[0].size() || matrix[x][y] != 1) return false;
return true;
}
void bfs(int x, int y, vector<vector<int> >& matrix, int& sum){
if(!checkLocation(x, y, matrix)) return;
int width = matrix[0].size();
deque<int> queue;
queue.push_back(x*width+y);
while(!queue.empty()){
int cur = queue.front();
queue.pop_front();
int idx_x = cur / width;
int idx_y = cur % width;
matrix[idx_x][idx_y] = 2;
if(checkLocation(idx_x-1, idx_y, matrix)){
queue.push_back( (idx_x-1) * width + idx_y );
}
if(checkLocation(idx_x+1, idx_y, matrix)){
queue.push_back( (idx_x+1) * width + idx_y);
}
if(checkLocation(idx_x, idx_y+1, matrix)){
queue.push_back( idx_x * width + idx_y + 1 );
}
if(checkLocation(idx_x, idx_y-1, matrix)){
queue.push_back( idx_x * width + idx_y - 1);
}
}
sum++;
}
int findIslandNum(const vector<vector<int> >& matrix){
vector<vector<int> > cache = matrix;
int sum = 0;
for(int i=0; i< matrix.size(); i++){
for(int j=0; j<matrix[0].size();j++){
bfs(i, j, cache, sum);
}
}
return sum;
}
void islandWaterTest(){
vector<vector<int> > matrix {{1,0,0,1,0},{1,0,0,0,0},{1,1,1,1,0},{0,0,1,1,1}};
cout << findIslandNum(matrix) <<endl;
}
My idea is a 3-dimensional dp
- liangdaleo February 12, 2015