Untitled
plain_text
a month ago
3.0 kB
0
Indexable
Never
#include<iostream> using namespace std; int T, hang, cot, vtdx, vtdy; int time[5][5], visit[5][5], diamond[5][5], fire_lake[5][5], out[5][5]; int front, rear; int n, x, y; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; int flag = 0, n_out, count1, rs; struct toado{ int x; int y; }; toado queue[10000000]; void init() { front = 0; rear = 0; } void push(int x, int y) { queue[rear].x = x; queue[rear].y = y; rear ++; } toado pop() { toado t = queue[front]; front ++; return t; } void bfs() { init(); for(int i = 0; i < hang; i ++) { for(int j = 0; j < cot; j ++) { if(!fire_lake[i][j]) { push(i, j); visit[i][j] = 1; } } } while(front < rear) { toado t = pop(); for(int i = 0; i < 4; i ++) { int xn = t.x + dx[i]; int yn = t.y + dy[i]; if(xn >= 0 && xn < hang && yn >= 0 && yn < cot && fire_lake[xn][yn] != 100000 && visit[xn][yn]==0) { push(xn, yn); fire_lake[xn][yn] = fire_lake[t.x][t.y] + 1; visit[xn][yn] = 1; } } } } void dequy(int x, int y, int check, int count1) { flag = 0; for(int i = 0; i < n_out; i ++) { if(x == out[i][0] && y == out[i][1]) { if(rs < count1) rs = count1; flag = 1; } } cout << x << " " << y << endl;; if(flag) return; for(int i = 0; i < 4; i ++) { int xn = x + dx[i]; int yn = y + dy[i]; if (xn >= 0 && xn < hang && yn >= 0 && yn < cot && visit[xn][yn] == 0) { if(fire_lake[xn][yn] != 100000 && check +1 < fire_lake[xn][yn]) { visit[xn][yn] = 1; dequy(xn, yn, check + 1, count1 + diamond[xn][yn]); visit[xn][yn] = 0; } else if(fire_lake[xn][yn] == 100000) { visit[xn][yn] = 1; dequy(xn, yn, check + 2, count1 + diamond[xn][yn]); visit[xn][yn] = 0; } } } } int main() { freopen("input.txt", "r", stdin); ios::sync_with_stdio(false); cin >> T; for(int test_case = 1; test_case <= T; test_case ++) { cin >> hang >> cot; cin >> vtdx >> vtdy; vtdy --; vtdx --; for(int i = 0; i < hang; i ++) { for(int j = 0; j < cot; j ++) { visit[i][j] = 0; diamond[i][j] = 0; fire_lake[i][j] = 10000; out[i][j] = 0; } } //chay cin >> n; for(int i = 0; i < n; i ++) { cin >> x >> y; fire_lake[x-1][y-1] = 0; } //ho cin >> n; for(int i = 0; i < n; i ++) { cin >> x >> y; fire_lake[x-1][y-1] = 100000; } //thoat cin >> n_out; for(int i = 0; i < n; i ++) { cin >> x >> y; out[x-1][y-1] = 1; } //kc for(int i = 0; i < hang; i ++) { for(int j = 0; j < cot; j ++) { cin >> diamond[i][j]; } } rs = 0; count1 = 0; bfs(); for(int i = 0; i < hang; i ++) { for(int j = 0; j < cot; j ++) { visit[i][j] = 0; cout << fire_lake[i][j] << "\t"; } cout << endl; } visit[vtdx][vtdy] = 1; dequy(vtdx, vtdy, 0, diamond[vtdx][vtdy]); cout << "Case #" << test_case << endl << rs << endl; } return 0; }