Round C APAC Test 2017 Problem A. Monster Path (C++)

2019-11-08 01:12:36

字體：大中小

來源：轉載

供稿：網友

PRoblem

Codejamon is a mobile game in which monster trainers walk around in the real world to catch monsters. You have an old smartphone with a short battery life, so you need to choose your path carefully to catch as many monsters as possible.

Suppose the Codejamon world is a rectangular grid with R rows and C columns. Rows are numbered from top to bottom, starting from 0; columns are numbered from left to right, starting from 0. You start in the cell in the Rsth row and the Csth column. You will take a total of S unit steps; each step must be to a cell sharing an edge (not just a corner) with your current cell.

Whenever you take a step into a cell in which you have not already caught a monster, you will catch the monster in that cell with probability P if the cell has a monster attractor, or Q otherwise. If you do catch the monster in a cell, it goes away, and you cannot catch any more monsters in that cell, even on future visits. If you do not catch the monster in a cell, you may still try to catch the monster on a future visit to that cell. The starting cell is special: you have no chance of catching a monster there before taking your first step.

If you plan your path optimally before making any move, what is the maximum possible expected number of monsters that you will be able to catch?

The battery can only support limited steps, so hurry up! Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case starts with a line of five integers: R, C, Rs, Cs and S. R and C are the numbers of rows and columns in the grid; Rs and Cs are the numbers of the row and column of your starting position, and S is the number of steps you are allowed to take.

The next line contains two decimals P and Q, where P is the probability of meeting a monster in cells with a monster attractor, and Q is the probability of meeting a monster in cells without a monster attractor. P and Q are each given to exactly four decimal places.

Each of the next R lines contains contains C space-separated characters; the j-th character of the i-th line represents the cell at row i and column j. Each element is either . (meaning there is no attractor in that cell) or A (meaning there is an attractor in that cell).

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the largest possible expected number of monsters that the player can catch in the given amount of steps.

y will be considered correct if y is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Limits

1 ≤ T ≤ 100. 0 ≤ Rs < R. 0 ≤ Cs < C. 0 ≤ Q < P ≤ 1. Small dataset

1 ≤ R ≤ 10. 1 ≤ C ≤ 10. 0 ≤ S ≤ 5. Large dataset

1 ≤ R ≤ 20. 1 ≤ C ≤ 20. 0 ≤ S ≤ 9.

分析：

廣度優先算法。遞歸進行，每步記錄：當前剩余步數step、當前期望值cur、當前位置(i, j)、當前訪問過的網格狀態visited。一旦剩余步數為step==0，則將cur與全局result相比，取大值。每一步向上、下、左、右4個方向遞歸(注意越界)，并在cur上加上相應可能性，調整當前位置，更新網格狀態visited，即在當前位置上+1，說明該位置訪問過過visited[i][j]次（計算要加上的相應可能性時需要用）。計算每步cur的增量：假設該位置之前訪問過x次。若有attractor，則當前增量=[(1-P)^(x)]*P, 其中[(1-P)^(x)]表示之前x次沒抓到monster的概率。若無attractor，則相應增量=[(1-Q)^x]*Q

代碼：Github

#include <iostream>#include <cmath>#include <vector>#include <stack>#include <queue>#include <algorithm>#include <fstream>#include <iomanip>using namespace std;typedef long long ll;int T;int R, C, Rs, Cs, S;double p;double q;double result = 0;void solve(double cur, int i, int j, int step, vector<vector<char>>game, vector<vector<int>> visited) { if (step == 0) { result = max(result, cur); return; } if (i - 1 >= 0) { visited[i - 1][j]++; if (game[i - 1][j] == '.') solve(cur + pow((1 - q), (double)(visited[i - 1][j]) - 1)*q, i - 1, j, step - 1, game, visited); else solve(cur + pow((1 - p), (double)(visited[i - 1][j]) - 1)*p, i - 1, j, step - 1, game, visited); visited[i - 1][j]--; } if (j - 1 >= 0) { visited[i][j - 1]++; if (game[i][j - 1] == '.') solve(cur + pow((1 - q), (double)(visited[i][j - 1]) - 1)*q, i, j - 1, step - 1, game, visited); else solve(cur + pow((1 - p), (double)(visited[i][j - 1]) - 1)*p, i, j - 1, step - 1, game, visited); visited[i][j - 1]++; } if (i + 1 < R) { visited[i + 1][j]++; if (game[i + 1][j] == '.') solve(cur + pow((1 - q), (double)(visited[i + 1][j]) - 1)*q, i + 1, j, step - 1, game, visited); else solve(cur + pow((1 - p), (double)(visited[i + 1][j]) - 1)*p, i + 1, j, step - 1, game, visited); visited[i + 1][j]--; } if (j + 1 <C) { visited[i][j + 1]++; if (game[i][j + 1] == '.') solve(cur + pow((1 - q), (double)(visited[i][j + 1]) - 1)*q, i, j + 1, step - 1, game, visited); else solve(cur + pow((1 - p), (double)(visited[i][j + 1]) - 1)*p, i, j + 1, step - 1, game, visited); visited[i][j + 1]++; }}int main() { ifstream f_input; ofstream f_output; f_input.open("A-large-practice.in"); f_output.open("out_put"); f_input >> T; for (int tt = 1; tt <= T; tt++) { result = 0; f_input >> R >> C >> Rs >> Cs >> S; f_input >> p >> q; vector<vector<char>> game(R, vector<char>(C, '.')); for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) f_input >> game[i][j]; vector<vector<int>> visited(R, vector<int>(C, 0)); solve(0, Rs, Cs, S, game, visited); f_output << "Case #" << tt << ": "; f_output.setf(ios::fixed, ios::floatfield); f_output << setprecision(7); f_output<< result << endl; cout << tt << "finished" << endl; } f_input.close(); f_output.close();}

上一篇：C++復制構造函數參數類型的探討

下一篇：C++中類的大小計算方法總結