#include #include #include #include using namespace std; const int MAXN = 1005; long long n, m, A, B; long long values[MAXN][MAXN]; string a[MAXN], aCopy[MAXN]; string answer[MAXN]; long long current = 0; long long maxResult = 0, bestStart = 0; int startTime; /* 0 -. down 1 -. up 2 -. left 3 -. right */ int lastI, lastJ, lastD; void simulate(int i, int j, int d) { //cout << i << " " << j << " --> " << current << '\n'; if(i<0 || j<0 || i>=n || j>=m) return; current += values[i][j]; lastI = i; lastJ = j; lastD = d; if(a[i][j]=='/') { if(d==0) d = 2; else if(d==1) d = 3; else if(d==2) d = 0; else if(d==3) d = 1; } else if(a[i][j]=='\\') { if(d==0) d = 3; else if(d==1) d = 2; else if(d==2) d = 1; else if(d==3) d = 0; } if(d==0) simulate(i+1, j, d); else if(d==1) simulate(i-1, j, d); else if(d==2) simulate(i, j-1, d); else if(d==3) simulate(i, j+1, d); } int convert(char a, char b) { if(a==b) return 0; if(a!='.') return B; return A; } void bruteForce(int startRow, int penalty, int last) { if(clock()>4955 || clock()-startTime>200) return; //cout << startRow << " ----- " << penalty << '\n'; int t; int li, lj; current = penalty; simulate(startRow, 0, 3); t = current; li = lastI;lj = lastJ; if(current<=last) return; if(current>maxResult) { maxResult = current; bestStart = startRow; for(int i = 0;i> n >> m; cin >> A >> B; for(int i = 0;i> a[i]; aCopy[i] = a[i]; answer[i] = a[i]; } for(int i = 0;i> values[i][j]; for(int i = 0;imaxResult) { maxResult = current; bestStart = i; } } } for(int row = 0;row4800) break; if( (n*m*n*4<1e9) || (n*m*4<(1e9 + 8*1e8) && chance<=75) || ( n*m*4<(2*1e9) && chance<=50) || ( n*m*4<(1e8) && chance<=10) ) { for(int i = 0;i