fgd
unknown
plain_text
10 months ago
3.0 kB
2
Indexable
Never
#include <iostream> using namespace std; int T, N, M, SR, SC; int F, L, E; int arr[20][20]; bool visited[20][20]; int diamond[20][20]; int tmp[20][20]; bool lake[20][20]; int ans, maxA; bool Exit[20][20]; int nextTime; class Queue{ public: int front, rear; int q[10000]; Queue(); void enQueue(int value); int deQueue(); void reset(); bool is_Empty(); }; Queue::Queue(){ front = -1; rear = -1; } void Queue::enQueue(int value){ q[++rear] = value; } int Queue::deQueue(){ return q[++front]; } void Queue::reset(){ front = -1; rear = -1; } bool Queue::is_Empty(){ return front == rear; } int X[4] = {-1, 1, 0, 0}; int Y[4] = {0, 0, -1, 1}; Queue rQueue, cQueue; void expand(){ while(rQueue.is_Empty() == false){ int cr = rQueue.deQueue(); int cc = cQueue.deQueue(); for(int i = 0; i < 4; i++){ int nr = cr + X[i]; int nc = cc + Y[i]; if(nr >= 0 && nr < N && nc >= 0 && nc < M && lake[nr][nc] == 0 && tmp[nr][nc] == 1000000){ tmp[nr][nc] = tmp[cr][cc] + 1; rQueue.enQueue(nr); cQueue.enQueue(nc); } } } } void backtrack(int row, int col, int tm){ if(Exit[row][col]){ if(ans > maxA){ maxA = ans; } } for(int i = 0; i < 4; i++){ int nrow = row + X[i]; int ncol = col + Y[i]; if(nrow >= 0 && nrow < N && ncol >= 0 && ncol < M && visited[nrow][ncol] == false){ if(lake[nrow][ncol] == false){ nextTime = tm + 1; if(nextTime < tmp[nrow][ncol]){ ans += diamond[nrow][ncol]; visited[nrow][ncol] = true; backtrack(nrow, ncol, nextTime); ans -= diamond[nrow][ncol]; visited[nrow][ncol] = false; } }else{ nextTime = tm + 2; if(nextTime < tmp[nrow][ncol]){ ans += diamond[nrow][ncol]; visited[nrow][ncol] = true; backtrack(nrow, ncol, nextTime); ans -= diamond[nrow][ncol]; visited[nrow][ncol] = false; } } } } } int main(){ cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> N >> M >> SR >> SC; SR--, SC--; arr[SR][SC] = 0; int x, y; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ tmp[i][j] = 1000000; visited[i][j] = false; Exit[i][j] = false; lake[i][j] = false; } } rQueue.reset(); cQueue.reset(); cin >> F; for(int i = 0; i < F; i++){ cin >> x >> y; x--; y--; rQueue.enQueue(x); cQueue.enQueue(y); tmp[x][y] = 0; } cin >> L; for(int i = 0; i < L; i++){ cin >> x >> y; x--; y--; lake[x][y] = true; } cin >> E; for(int i = 0; i < E; i++){ cin >> x >> y; x--; y--; Exit[x][y] = true; } for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cin >> diamond[i][j]; } } ans = diamond[SR][SC]; visited[SR][SC] = true; expand(); maxA = -1; backtrack(SR, SC, 0); cout << "Case #" << tc << endl; cout << maxA << endl; } return 0; }
Leave a Comment