#include #include #include #include #include #include #include #include #include #include #include #include namespace patch { template std::string to_string(const T& n) { std::ostringstream stm; stm << n; return stm.str(); } } using std::sort; using std::cin; using std::cout; using std::endl; using std::vector; using std::map; using std::set; using std::min; using std::pair; using std::string; using std::make_pair; using std::priority_queue; const time_t TL = 4700; time_t curTime; inline bool TimeUp() { return (clock() - curTime > TL); } const int MAT_SIZE = 400 + 5; const int ARR_SIZE = 400 * 400 + 5; const int STATE_LIMIT = 400; const int NEW_STATES_LIMIT = 50; int n, m; int a, c; char field[MAT_SIZE][MAT_SIZE]; long long points[MAT_SIZE][MAT_SIZE]; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int maxSc; struct State { bool done; int bestStart; char mat[MAT_SIZE][MAT_SIZE]; }; State* bestState; State* bestState1; State* bestState2; bool hit[MAT_SIZE][MAT_SIZE]; bool changed[MAT_SIZE][MAT_SIZE]; void Output(State* node) { cout << node->bestStart + 1 << endl; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cout << node->mat[i][j]; } cout << endl; } } void Input() { cin >> n >> m; cin >> a >> c; bestState = new State; bestState1 = new State; bestState2 = new State; for(int i = 0; i < n; i++) cin >> field[i]; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> points[i][j]; maxSc += points[i][j]; bestState->mat[i][j] = field[i][j]; bestState1->mat[i][j] = field[i][j]; bestState2->mat[i][j] = field[i][j]; } } } long long curSt1; long long best1 = 0; long long bestDc1 = INT_MAX; int bestDp1 = 1; bool done1; bool ret1; int bk1 = -5000; time_t TB = 0; long long curSt; long long best = 0; long long bestDc = INT_MAX; int bestDp = 1; bool done; bool ret; int bk = -5000; /// 0 -> down /// 1 -> up /// 2 -> right /// 3 -> left void Solve(int i, int j, int to, long long score, int dp, int lw, long long dec) { if(TimeUp()) { if(best > best1) Output(bestState); else Output(bestState1); exit(0); } if(clock() - curTime > TB) done = true; if(done) return; if(score < bk or lw > 3) return; if(i >= n or i < 0 or j >= m or j < 0) { if(score > best) { bestState->bestStart = curSt; best = score; bk = -best; bestDp = dp; bestDc = dec; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { bestState->mat[i][j] = field[i][j]; } } } return; } if(changed[i][j] or hit[i][j]) Solve(i + dir[to][0], j + dir[to][1], to, score + points[i][j], dp + 1, 0, dec); else { if(field[i][j] == '/') { hit[i][j] = true; switch(to) { case 0: Solve(i, j - 1, 3, score + points[i][j], dp + 1, 0, dec); break; case 1: Solve(i, j + 1, 2, score + points[i][j], dp + 1, 0, dec); break; case 2: Solve(i - 1, j, 1, score + points[i][j], dp + 1, 0, dec); break; case 3: Solve(i + 1, j, 0, score + points[i][j], dp + 1, 0, dec); break; } changed[i][j] = true; field[i][j] = '\\'; switch(to) { case 0: Solve(i, j + 1, 2, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 1: Solve(i, j - 1, 3, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 2: Solve(i + 1, j, 0, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 3: Solve(i - 1, j, 1, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; } changed[i][j] = false; field[i][j] = '/'; hit[i][j] = false; } else if(field[i][j] == '\\') { hit[i][j] = true; switch(to) { case 0: Solve(i, j + 1, 2, score + points[i][j], dp + 1, 0, dec); break; case 1: Solve(i, j - 1, 3, score + points[i][j], dp + 1, 0, dec); break; case 2: Solve(i + 1, j, 0, score + points[i][j], dp + 1, 0, dec); break; case 3: Solve(i - 1, j, 1, score + points[i][j], dp + 1, 0, dec); break; } changed[i][j] = true; field[i][j] = '/'; switch(to) { case 0: Solve(i, j - 1, 3, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 1: Solve(i, j + 1, 2, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 2: Solve(i - 1, j, 1, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 3: Solve(i + 1, j, 0, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; } changed[i][j] = false; field[i][j] = '\\'; hit[i][j] = false; } else if(field[i][j] == '.') { hit[i][j] = true; Solve(i + dir[to][0], j + dir[to][1], to, score + points[i][j], dp + 1, 0, dec); changed[i][j] = true; field[i][j] = '/'; switch(to) { case 0: Solve(i, j - 1, 3, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 1: Solve(i, j + 1, 2, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 2: Solve(i - 1, j, 1, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 3: Solve(i + 1, j, 0, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; } field[i][j] = '\\'; switch(to) { case 0: Solve(i, j + 1, 2, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 1: Solve(i, j - 1, 3, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 2: Solve(i + 1, j, 0, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 3: Solve(i - 1, j, 1, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; } changed[i][j] = false; field[i][j] = '.'; hit[i][j] = false; } } } void Solve1(int i, int j, int to, long long score, int dp, int lw, long long dec) { if(TimeUp()) { if(best > best1) Output(bestState); else Output(bestState1); exit(0); } if(clock() - curTime > TB) done1 = true; if(done1) return; if(score < bk1 or lw > 5) return; if(3*dec > score) return; if(i >= n or i < 0 or j >= m or j < 0) { if(score > best1) { bestState1->bestStart = curSt1; best1 = score; bk1 = -best1; bestDp1 = dp; bestDc1 = dec; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { bestState1->mat[i][j] = field[i][j]; } } } return; } if(changed[i][j] or hit[i][j]) Solve1(i + dir[to][0], j + dir[to][1], to, score + points[i][j], dp + 1, 0, dec); else { if(field[i][j] == '/') { hit[i][j] = true; switch(to) { case 0: Solve1(i, j - 1, 3, score + points[i][j], dp + 1, 0, dec); break; case 1: Solve1(i, j + 1, 2, score + points[i][j], dp + 1, 0, dec); break; case 2: Solve1(i - 1, j, 1, score + points[i][j], dp + 1, 0, dec); break; case 3: Solve1(i + 1, j, 0, score + points[i][j], dp + 1, 0, dec); break; } changed[i][j] = true; field[i][j] = '\\'; switch(to) { case 0: Solve1(i, j + 1, 2, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 1: Solve1(i, j - 1, 3, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 2: Solve1(i + 1, j, 0, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 3: Solve1(i - 1, j, 1, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; } changed[i][j] = false; field[i][j] = '/'; hit[i][j] = false; } else if(field[i][j] == '\\') { hit[i][j] = true; switch(to) { case 0: Solve1(i, j + 1, 2, score + points[i][j], dp + 1, 0, dec); break; case 1: Solve1(i, j - 1, 3, score + points[i][j], dp + 1, 0, dec); break; case 2: Solve1(i + 1, j, 0, score + points[i][j], dp + 1, 0, dec); break; case 3: Solve1(i - 1, j, 1, score + points[i][j], dp + 1, 0, dec); break; } changed[i][j] = true; field[i][j] = '/'; switch(to) { case 0: Solve(i, j - 1, 3, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 1: Solve(i, j + 1, 2, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 2: Solve(i - 1, j, 1, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; case 3: Solve(i + 1, j, 0, score + points[i][j] - c, dp + 1, (points[i][j] >= c)? 0 : lw + 1, dec + c); break; } changed[i][j] = false; field[i][j] = '\\'; hit[i][j] = false; } else if(field[i][j] == '.') { hit[i][j] = true; Solve1(i + dir[to][0], j + dir[to][1], to, score + points[i][j], dp + 1, 0, dec); changed[i][j] = true; field[i][j] = '/'; switch(to) { case 0: Solve1(i, j - 1, 3, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 1: Solve1(i, j + 1, 2, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 2: Solve1(i - 1, j, 1, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 3: Solve1(i + 1, j, 0, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; } field[i][j] = '\\'; switch(to) { case 0: Solve1(i, j + 1, 2, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 1: Solve1(i, j - 1, 3, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 2: Solve1(i + 1, j, 0, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; case 3: Solve1(i - 1, j, 1, score + points[i][j] - a, dp + 1, (points[i][j] >= a)? 0 : lw + 1, dec + a); break; } changed[i][j] = false; field[i][j] = '.'; hit[i][j] = false; } } } bool used[MAT_SIZE]; int main() { std::iostream::sync_with_stdio(false); cin.tie(NULL); curTime = clock(); srand(time(NULL)); freopen("pinball.in", "r", stdin); freopen("pinball.out", "w", stdout); Input(); srand(time(NULL)); for(int i = 0; i < n; i++) { if(field[i][0] != '.') continue; int row = i; if(n * m > 20 * 20) row = rand() % n; if(used[row] or field[row][0] != '.') { continue; } used[row] = true; TB += 200; done = false, curSt = row, Solve(row, 0, 2, 0, 1, 0, 0); TB += 200; done1 = false, curSt1 = row, Solve1(row, 0, 2, 0, 1, 0, 0); } while(true) { if(TimeUp()) { if(best > best1) Output(bestState); else Output(bestState1); exit(0); } int row = rand() % n; if(used[row]) { continue; } used[row] = true; TB += 200; done = false, curSt = row, Solve(row, 0, 2, 0, 1, 0, 0); TB += 200; done1 = false, curSt1 = row, Solve1(row, 0, 2, 0, 1, 0, 0); } if(best > best1) Output(bestState); else Output(bestState1); return 0; }