#include #include // #include #include using namespace std; enum dir { Up, Right, Down, Left }; int N, M, A, C; long long sum; char **m, **final; int **LR, **RL, **UD, **DU; int **p; bool **v; clock_t start; const clock_t TC = 4.9 * CLOCKS_PER_SEC; void process(int r, int c, dir d) { // cout << "Row:" << r << " Col:" << c << " Dir:" << d << "; CURSUM=" << sum << endl; int cursum = -1, bestsum = 0; int row, col; dir bestdir; bool hasUnv; // row if(d == Right) { for(int j = c; j < M; ++j) { //if(m[r][j] == '.' && final[r][j] != '.') // now we don't have an object but we have had in the past if(v[r][j]) { continue; } // up hasUnv = 1; for(row = r; row > 0 && (m[row][j] == '.' || row == r); hasUnv &= v[row--][j]); hasUnv &= v[row][j]; if(hasUnv) // the whole path has been used so we can't place an object { continue; } cursum = DU[row][j] - DU[r][j];// cout << "col sum=" << cursum;// col sum cursum += RL[r][c] - RL[r][j];// cout << " row sum=" << RL[r][c] - RL[r][j];// row sum cursum += p[r][j];// cout << " cell sum=" << p[r][j];// cell sum if(m[r][j] == '.') { cursum -= A; } else if(m[r][j] == '\\') { cursum -= C; } if(cursum > bestsum) { bestsum = cursum; col = j; bestdir = Up; } // cout << "; To (" << row << ", " << j << ") cursum=" << cursum << endl; // down hasUnv = 1; for(row = r; row < N-1 && (m[row][j] == '.' || row == r); hasUnv &= v[row++][j]); hasUnv &= v[row][j]; if(hasUnv) // the whole path has been used so we can't place an object { continue; } cursum = UD[row][j] - UD[r][j];// cout << "col sum=" << cursum; // col sum cursum += RL[r][c] - RL[r][j];// cout << " row sum=" << RL[r][c] - RL[r][j];// row sum cursum += p[r][j];// cout << " cell sum=" << p[r][j];// cell sum if(m[r][j] == '.') { cursum -= A; } else if(m[r][j] == '/') { cursum -= C; } if(cursum > bestsum) { bestsum = cursum; col = j; bestdir = Down; } // cout << "; To (" << row << ", " << j << ") cursum=" << cursum << endl; // if(m[r][j] != '.') { break; } } // we can't place an object anywhere if(cursum == -1 || clock() - start >= TC) // exit! { return; } // update m & final final[r][col] = (bestdir == Up) ? '/' : '\\'; // sum += LR[r][col] - LR[r][c] - (m[r][col] == '.' ? A : (final[r][col] == m[r][col] ? 0 : C)); // TO BE COMMENTED IN PRODUCTION m[r][col] = '.'; // cout << "From (" << r << ", " << c << ") to (" << r << ", " << col << "); bestsum=" << bestsum << endl; // mark path for(int j = c; j <= col; ++j) { v[r][j] = 1; } // continue path process(r, col, bestdir); } else if(d == Left) { for(int j = c; j >= 0; --j) { //if(m[r][j] == '.' && final[r][j] != '.') // now we don't have an object but we have had in the past if(v[r][j]) { continue; } // up hasUnv = 1; for(row = r; row > 0 && (m[row][j] == '.' || row == r); hasUnv &= v[row--][j]); hasUnv &= v[row][j]; if(hasUnv) // the whole path has been used so we can't place an object { continue; } cursum = DU[row][j] - DU[r][j]; // col sum cursum += LR[r][c] - LR[r][j]; // row sum cursum += p[r][j]; // cell sum if(m[r][j] == '.') { cursum -= A; } else if(m[r][j] == '/') { cursum -= C; } if(cursum > bestsum) { bestsum = cursum; col = j; bestdir = Up; } // cout << "To (" << row << ", " << j << ") cursum=" << cursum << endl; // down hasUnv = 1; for(row = r; row < N-1 && (m[row][j] == '.' || row == r); hasUnv &= v[row++][j]); hasUnv &= v[row][j]; if(hasUnv) // the whole path has been used so we can't place an object { continue; } cursum = UD[row][j] - UD[r][j]; // col sum cursum += LR[r][c] - LR[r][j]; // row sum cursum += p[r][j]; // cell sum if(m[r][j] == '.') { cursum -= A; } else if(m[r][j] == '\\') { cursum -= C; } if(cursum > bestsum) { bestsum = cursum; col = j; bestdir = Down; } // cout << "To (" << row << ", " << j << ") cursum=" << cursum << endl; // if(m[r][j] != '.') { break; } } // we can't place an object anywhere if(cursum == -1 || clock() - start >= TC) // exit! { // cout << " cursum=" << cursum << endl; return; } // update m & final final[r][col] = (bestdir == Up) ? '\\' : '/'; // sum += RL[r][col] - RL[r][c] - (m[r][col] == '.' ? A : (final[r][col] == m[r][col] ? 0 : C)); // TO BE COMMENTED IN PRODUCTION m[r][col] = '.'; // cout << "From (" << r << ", " << c << ") to (" << r << ", " << col << "); bestsum=" << bestsum << endl; // mark path for(int j = c; j >= col; --j) { v[r][j] = 1; } // continue path process(r, col, bestdir); } // col else if(d == Down) { for(int i = r; i < N; ++i) { //if(m[i][c] == '.' && final[i][c] != '.') // now we don't have an object but we have had in the past if(v[i][c]) { continue; } // left hasUnv = 1; for(col = c; col > 0 && (m[i][col] == '.' || col == c); hasUnv &= v[i][col--]); hasUnv &= v[i][col]; if(hasUnv) // the whole path has been used so we can't place an object { continue; } cursum = RL[i][col] - RL[i][c]; // row sum cursum += DU[r][c] - DU[i][c]; // col sum cursum += p[i][c]; if(m[i][c] == '.') { cursum -= A; } else if(m[i][c] == '\\') { cursum -= C; } if(cursum > bestsum) { bestsum = cursum; row = i; bestdir = Left; } // cout << "To (" << i << ", " << col << ") cursum=" << cursum << endl; // right hasUnv = 1; for(col = c; col < M-1 && (m[i][col] == '.' || col == c); hasUnv &= v[i][col++]); hasUnv &= v[i][col]; if(hasUnv) // the whole path has been used so we can't place an object { continue; } cursum = LR[i][col] - LR[i][c]; // row sum cursum += DU[r][c] - DU[i][c]; // col sum cursum += p[i][c]; if(m[i][c] == '.') { cursum -= A; } else if(m[i][c] == '/') { cursum -= C; } if(cursum > bestsum) { bestsum = cursum; row = i; bestdir = Right; } // cout << "To (" << i << ", " << col << ") cursum=" << cursum << endl; // if(m[i][c] != '.') { break; } } // we can't place an object anywhere if(cursum == -1 || clock() - start >= TC) // exit! { return; } // update m & final final[row][c] = (bestdir == Left) ? '/' : '\\'; // sum += UD[row][c] - UD[r][c] - (m[row][c] == '.' ? A : (final[row][c] == m[row][c] ? 0 : C)); // TO BE COMMENTED IN PRODUCTION m[row][c] = '.'; // cout << "From (" << r << ", " << c << ") to (" << row << ", " << c << "); bestsum=" << bestsum << endl;//sum += bestsum;//INCORRECT // mark path for(int i = r; i <= row; ++i) { v[i][c] = 1; } // continue path process(row, c, bestdir); } else // if(d == Up) { for(int i = r; i >= 0; --i) { //if(m[i][c] == '.' && final[i][c] != '.') // now we don't have an object but we have had in the past if(v[i][c]) { continue; } // left hasUnv = 1; for(col = c; col > 0 && (m[i][col] == '.' || col == c); hasUnv &= v[i][col--]); hasUnv &= v[i][col]; if(hasUnv) // the whole path has been used so we can't place an object { continue; } cursum = RL[i][col] - RL[i][c]; // row sum cursum += UD[r][c] - UD[i][c]; // col sum cursum += p[i][c]; if(m[i][c] == '.') { cursum -= A; } else if(m[i][c] == '/') { cursum -= C; } if(cursum > bestsum) { bestsum = cursum; row = i; bestdir = Left; } // cout << "To (" << i << ", " << col << ") cursum=" << cursum << endl; // right hasUnv = 1; for(col = c; col < M-1 && (m[i][col] == '.' || col == c); hasUnv &= v[i][col++]); hasUnv &= v[i][col]; if(hasUnv) // the whole path has been used so we can't place an object { continue; } cursum = LR[i][col] - LR[i][c]; // row sum cursum += UD[r][c] - UD[i][c]; // col sum cursum += p[i][c]; if(m[i][c] == '.') { cursum -= A; } else if(m[i][c] == '\\') { cursum -= C; } if(cursum > bestsum) { bestsum = cursum; row = i; bestdir = Right; } // cout << "To (" << i << ", " << col << ") cursum=" << cursum << endl; // if(m[i][c] != '.') { break; } } // we can't place an object anywhere if(cursum == -1 || clock() - start >= TC) // exit! { return; } // update m & final final[row][c] = (bestdir == Left) ? '\\' : '/'; // sum += DU[row][c] - DU[r][c] - (m[row][c] == '.' ? A : (final[row][c] == m[row][c] ? 0 : C)); // TO BE COMMENTED IN PRODUCTION m[row][c] = '.'; // cout << "From (" << r << ", " << c << ") to (" << row << ", " << c << "); bestsum=" << bestsum << endl; // mark path for(int i = r; i >= row; --i) { v[i][c] = 1; } // continue path process(row, c, bestdir); } } int main() { start = clock(); ifstream inp; inp.open("pinball.in"); inp >> N >> M; inp >> A >> C; // cout << "N=" << N << " M=" << M << " A=" << A << " C=" << C << endl; m = new char*[N]; final = new char*[N]; inp.ignore(2, '\n'); for(int i = 0; i < N; ++i) { m[i] = new char[M]; final[i] = new char[M]; for(int j = 0; j < M; ++j) { inp.get(m[i][j]); final[i][j] = m[i][j]; } inp.ignore(2, '\n'); } p = new int*[N]; for(int i = 0; i < N; ++i) { p[i] = new int[M]; for(int j = 0; j < M; ++j) { inp >> p[i][j]; } } inp.close(); v = new bool*[N]; for(int i = 0; i < N; ++i) { v[i] = new bool[M]; memset(v[i], 0, M); /* for(int j = 0; j < M; ++j) { v[i][j] = 0; } */ } // computing cumulative matrices LR = new int*[N]; RL = new int*[N]; UD = new int*[N]; DU = new int*[N]; for(int i = 0; i < N; ++i) { UD[i] = new int[M]; DU[i] = new int[M]; } for(int i = 0; i < N; ++i) { LR[i] = new int[M]; LR[i][0] = p[i][0]; for(int j = 1; j < M; ++j) { LR[i][j] = LR[i][j - 1] + p[i][j]; } } for(int i = 0; i < N; ++i) { RL[i] = new int[M]; RL[i][M - 1] = p[i][M - 1]; for(int j = M - 2; j >= 0; --j) { RL[i][j] = RL[i][j + 1] + p[i][j]; } } for(int j = 0; j < M; ++j) { UD[0][j] = p[0][j]; for(int i = 1; i < N; ++i) { UD[i][j] = UD[i - 1][j] + p[i][j]; } } for(int j = 0; j < M; ++j) { DU[N - 1][j] = p[N - 1][j]; for(int i = N - 2; i >= 0; --i) { DU[i][j] = DU[i + 1][j] + p[i][j]; } } /* for(int i = 0; i < N; ++i) { for(int j = 0; j < M; ++j) { cout << m[i][j]; } cout << endl; } cout << endl; for(int i = 0; i < N; ++i) { for(int j = 0; j < M; ++j) { cout << p[i][j] << " "; } cout << endl; } cout << endl; */ // finding the starting row int row = 0, col;//, bestcol = 0; sum = 0; for(int i = 0; i < N; ++i) { for(col = 0; col < M-1 && m[i][col] == '.'; ++col); if(LR[i][col] > sum) { sum = LR[i][col]; row = i; // bestcol = col; } /* else if(LR[col] == sum) { if(col > bestcol) { row = i; bestcol = col; } } */ } // we have found the starting row; now we decide to where to continue sum = p[row][0]; process(row, 0, Right); // cout << "SUM = " << sum << endl; ofstream out; out.open("pinball.out"); out << row + 1 << '\n'; for(int i = 0; i < N; ++i) { for(int j = 0; j < M; ++j) { out << final[i][j]; } out << '\n'; } out.close(); // cout << "Elapsed time: " << (float)(clock() - start) / CLOCKS_PER_SEC << endl; return 0; }