Untitled
unknown
plain_text
a year ago
2.4 kB
3
Indexable
#include<iostream> using namespace std; int n, m, sr, sc; int fire, lake, exi; int F[600], L[600], E[600]; int M[20][20], A[20][20]; int S[2][100000]; int top, bot; int visited[20][20]; int FL[20][20]; int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 }; int kq, maxx; bool checkexit; void back2(int tgian, int x, int y, int kq) { if (A[x][y] == 2) { if (kq > maxx) maxx = kq; checkexit = true; } for (int i = 0; i < 4; i++) { int xnew = x + dx[i], ynew = y + dy[i]; if (xnew >= 1 && xnew <= n && ynew >= 1 && ynew <= m) { if ((tgian + 1 < FL[xnew][ynew] || FL[xnew][ynew]<0 )&& visited[xnew][ynew] == 0) { visited[xnew][ynew] = 1; if (FL[xnew][ynew] == 9998) { back2(tgian + 2, xnew, ynew, kq + M[xnew][ynew]); visited[xnew][ynew] = 0; } else { back2(tgian + 1, xnew, ynew, kq + M[xnew][ynew]); visited[xnew][ynew] = 0; } } } } } int main() { int t; cin >> t; for (int tc = 1; tc <=t; tc++) { cin >> n >> m >> sr >> sc; cin >> fire; for (int i = 0; i < 2 * fire; i++) cin >> F[i]; cin >> lake; for (int i = 0; i < 2 * lake; i++) cin >> L[i]; cin >> exi; for (int i = 0; i < 2 * exi; i += 2) { cin >> E[i] >> E[i + 1]; A[E[i]][E[i + 1]] = 2; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> M[i][j]; visited[i][j] = 0; FL[i][j] = 0; } } for (int i = 0; i < 2 * lake; i += 2) { FL[L[i]][L[i + 1]] = 9999; } // top = bot = -1; // for (int i = 0; i < 2 * fire; i += 2) { //push vao queue top++; S[0][top] = F[i]; S[1][top] = F[i + 1]; FL[F[i]][F[i + 1]] = 1; } while (top != bot) { bot++; int x = S[0][bot]; int y = S[1][bot]; for (int k = 0; k < 4; k++) { int xnew = x + dx[k]; int ynew = y + dy[k]; if (FL[xnew][ynew] == 0 && xnew <= n && xnew >= 1 && ynew <= m && ynew >= 1) { top++; S[0][top] = xnew; S[1][top] = ynew; FL[xnew][ynew] = FL[x][y] + 1; } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) FL[i][j] = FL[i][j] - 1; } visited[sr][sc] = 1; kq = M[sr][sc]; maxx = 0; checkexit = false; back2(0, sr, sc, kq); cout << "Case #" << tc << endl; if (checkexit) cout << maxx << endl; else cout << -1 << endl; } return 0; }
Editor is loading...
Leave a Comment