Untitled
unknown
plain_text
a year ago
1.5 kB
6
Indexable
#include <iostream> #include <bits/stdc++.h> #include <cstring> #include<numeric> using namespace std; long long mod = 1e9+9; #define endl '\n' #define ll long long #define ull unsigned long long const int N = 105; char grid[N][N]; int scores[N][N]; int n,m,d; double p; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; /* up down right left */ bool valid(int i, int j) { if(i<0 || i>=n || j<0 || j>=m || grid[i][j]=='#') return 0; return 1; } double dfs(int x, int y, int move, double cum_p) { double now = cum_p*scores[x][y]; if(grid[x][y]=='*' || move>=d) return now; double scores_dir[4]; double other_p = 0.5*(1-p); for(int i=0;i<4;i++) { int next_x = x+dx[i], next_y = y+dy[i]; if(valid(next_x,next_y)) { scores_dir[i]= dfs(next_x,next_y,move+1,cum_p*p); } else { scores_dir[i]= dfs(x,y,move+1,cum_p*p); } } double ans=INT_MIN; for(int i=0;i<4;i++) ans= max(ans,max(scores_dir[i],scores_dir[i]*other_p/p)); return now+ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("test_input.txt","r",stdin); // freopen("test_output.txt","w",stdout); cin>>n>>m>>d>>p; int start_i,start_j; cin>>start_i>>start_j; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>grid[i][j]; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>scores[i][j]; cout<<fixed<<setprecision(6)<<dfs(start_i-1,start_j-1,0,1); }
Editor is loading...
Leave a Comment