Untitled
plain_text
a month ago
2.5 kB
1
Indexable
Never
#include<iostream> using namespace std; int n, m, sr, sc; int kvkc[20][20]; int kvh[20][20]; int kvc[20][20]; int lt[20][20]; int timee[20][20]; int vthgx, vthgy; int dx[] = {0, -1, 0, 1}; int dy[] = {-1, 0, 1, 0}; int front, rear; int visit[20][20]; int ltcx = 0, ltcy = 0; int maxx = -1; void init() { front = 0; rear = 0; } struct toado { int x, y; }; toado queu[500]; void push(int xx, int yy) { queu[rear].x = xx; queu[rear].y = yy; rear++; } toado pop() { toado t = queu[front]; front ++; return t; } void BFSC() { init(); for (int i = 1; i <= n; i++) { for (int j = 1; j <=m; j++) { if (kvc[i][j] == 1) { push(i, j); } } } int xn, yn; //kvc[x][y] = 1; while (front < rear) { toado vitri = pop(); for (int i = 0; i < 4; i++) { xn = vitri.x + dx[i]; yn = vitri.y + dy[i]; if (xn>0 && xn <= n && yn > 0 && yn <= m && kvh[xn][yn] == 1) { if (kvc[xn][yn] == 999999) { push(xn, yn); kvc[xn][yn] = kvc[vitri.x][vitri.y] + 1; } } } } } void backtrack(int h, int c, int count) { if (lt[h][c] == 1) { if (maxx < count) { maxx = count; } } for (int i = 0; i < 4; i++) { int xn = h + dx[i]; int yn = c + dy[i]; if (xn>0 && xn <= n && yn > 0 && yn <= m && visit[xn][yn] == 0 && kvc[xn][yn] > visit[h][c] + kvh[xn][yn]) { visit[xn][yn] = visit[h][c] + kvh[xn][yn]; backtrack(xn, yn, count + kvkc[xn][yn]); visit[xn][yn] = 0; } } } int main() { ios::sync_with_stdio(false); //freopen("input.txt", "r",stdin); int sl; cin >> sl; for (int stt = 1; stt <= sl; stt++) { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { kvc[i][j] = 999999; kvh[i][j] = 1; kvkc[i][j] = 0; visit[i][j] = 0; lt[i][j] = 0; } } cin >> vthgx >> vthgy; int slc, slh, xx, yy, slt; cin >> slc; for (int i = 1; i <= slc; i++) { cin >> xx >> yy; kvc[xx][yy] = 1; } cin >> slh; for (int i = 1; i <= slh; i++) { cin >> xx >> yy; kvh[xx][yy] = 2; } cin >> slt; for (int i = 1; i <= slt; i++) { cin >> xx >> yy; lt[xx][yy] = 1; ltcx = xx; ltcy = yy; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> kvkc[i][j]; } } BFSC(); maxx = -1; visit[vthgx][vthgy] = 1; backtrack(vthgx, vthgy, kvkc[vthgx][vthgy]); cout << "Case #"<<stt<<endl; cout << maxx <<endl; } return 0; }