Untitled
unknown
plain_text
2 years ago
3.3 kB
11
Indexable
// In Practice, You should use the statndard input/output #include<iostream> using namespace std; int const DOOR = 99999999; int const HO = 99999990; int map[16][16],diamond[16][16],n,m,fire[16][16],head,rear,lake,cong,res,dem,visit[16][16]; struct node{ int r; int c; node(){}; node(int _r, int _c){ r = _r; c = _c; ;} }; node q[300]; node hugo; node gate[300]; node h[4] = {node(-1,0),node(0,1),node(1,0),node(0,-1)}; void reset(){ head = -1; rear = -1; for (int i =1; i < 16; i++) { for (int k = 1; k < 16; k++) { fire[i][k] = -1; diamond[i][k] = 0; map[i][k] = 0; visit[i][k] = -1; } } } void input(){ cin>>n>>m; cin>>hugo.r>>hugo.c; int tmp; cin>>tmp; rear += tmp; for (int i = 0; i <= rear; i++) { cin>>q[i].r>>q[i].c; fire[q[i].r][q[i].c] = 0; } cin>>lake; for (int i = 0; i < lake; i++) { int r,c; cin>>r>>c; map[r][c] = HO; fire[r][c] = HO; } cin>>cong; for (int i = 0; i < cong; i++) { cin>>gate[i].r>>gate[i].c; } for (int i = 1; i <= n; i++) { for (int k = 1; k <= m; k++) { cin>>diamond[i][k]; } } } void bfsFire(){ while (rear > head) { head++; node t = q[head]; for (int i = 0; i < 4; i++) { node t1 = t; t1.r = t1.r + h[i].r; t1.c = t1.c + h[i].c; if (t1.r < 1 || t1.r > n || t1.c < 1 || t1.c > m) { continue; } if (map[t1.r][t1.c] == HO) { continue; } if (fire[t1.r][t1.c] == -1) { rear++; q[rear] = t1; fire[t1.r][t1.c] = fire[t.r][t.c] + 1; } } } } bool isGate(int hang,int cot){ for (int i = 0; i < cong; i++) { if (hang == gate[i].r && cot == gate[i].c) return true; } return false; } void dfs(int r, int c){ if (isGate(r,c)) { if (dem > res) res = dem; return; } if (visit[r][c] >= fire[r][c]) { return; } for (int i = 0; i < 4; i++) { node t = node(r,c); t.r = t.r + h[i].r; t.c = t.c + h[i].c; if (t.r < 1 || t.r > n || t.c < 1 || t.c > m)continue; if (map[r][c] == 0 && visit[t.r][t.c] == -1) { if (visit[r][c] + 1 < fire[t.r][t.c]) { visit[t.r][t.c] = visit[r][c] + 1; dem += diamond[t.r][t.c]; dfs(t.r,t.c); dem -= diamond[t.r][t.c]; visit[t.r][t.c] = visit[r][c] - 1; } } if (map[r][c] == HO && visit[t.r][t.c] == -1) { if (visit[r][c] + 2 < fire[t.r][t.c]) { visit[t.r][t.c] = visit[r][c] + 2; dem += diamond[t.r][t.c]; dfs(t.r,t.c); dem -= diamond[t.r][t.c]; visit[t.r][t.c] = visit[r][c] - 2; } } } } bool check(){ for (int i = 0; i < cong; i++) if (visit[gate[i].r][gate[i].c] != -1) return true; return false; } int main() { int test_case; int T; freopen("Text.txt", "r", stdin); cin >> T; for(test_case = 1; test_case <= T; ++test_case) { reset(); input(); bfsFire(); dem = 0; res = 0; visit[hugo.r][hugo.c] = 0; dem+=diamond[hugo.r][hugo.c]; dfs(hugo.r,hugo.c); if (check()) { cout << "#" << test_case << " " << res << endl; } // Print the answer to standard output(screen). } return 0;//Your program should return 0 on normal termination. }
Editor is loading...