104北市賽 搶救雷恩大兵

#include <cstdio>#include <cstring>#include <queue>#define NUM 21using namespace std; int s[NUM][NUM], t[NUM][NUM], map[NUM][NUM],ans[NUM][NUM][NUM][NUM]; int gor[4] = { 1,0,-1,0 }; //四個方向 int goc[4] = { 0,1,0,-1 }; //四個方向typedef struct _point { int r; int c; int w; }Point; struct cmp { bool operator()(const Point &a, const Point &b) { return a.w > b.w; } }; priority_queue <Point,vector<Point>,cmp > myq; int bound(int r, int c, int N) { if (((r>0) && (r <= N)) && ((c>0) && (c <= N))) return 1; else return 0; } int abso(int x, int y) { if (x>y) return x - y; else return y - x; } void bfs0(int r, int c, int i, int j, int N) {//(r,c)出發在(i,j)使用死光彈，所獲得到每一點的最小值 int tmp = map[i][j]; Point myp, nowp, nextp; memset(s, 0x7f, sizeof(s)); map[i][j] = 0; s[r][c] = map[r][c]; myp.r = r; myp.c = c; myp.w = s[r][c]; myq.push(myp); //加入queue中 while (myq.size()>0) { nowp = myq.top(); //取出queue的第一個 myq.pop(); //將queue的第一個刪除 for (int k = 0; k<4; k++) { //四個方向加入queue nextp.r = nowp.r + gor[k]; nextp.c = nowp.c + goc[k]; if ((bound(nextp.r, nextp.c, N)) && (s[nextp.r][nextp.c]>s[nowp.r][nowp.c] + map[nextp.r][nextp.c])) { //在地圖內，且發現比較小 s[nextp.r][nextp.c] = s[nowp.r][nowp.c] + map[nextp.r][nextp.c]; if (nextp.r == i && nextp.c == j) {//到達目的地就結束，清空Queue while (myq.size() > 0) { myq.pop(); } break; } myp.r = nextp.r; myp.c = nextp.c; myp.w = s[myp.r][myp.c]; myq.push(myp); //加入queue } } } map[i][j] = tmp; ans[r][c][i][j] = s[i][j]; } void bfs1(int r, int c, int i, int j, int N) {//(r,c)出發在(i,j)使用死光彈，所獲得到每一點的最小值 int tmp = map[i][j]; Point myp, nowp, nextp; memset(t, 0x7f, sizeof(t)); map[i][j] = 0; t[r][c] = map[r][c]; myp.r = r; myp.c = c; myp.w = t[r][c]; myq.push(myp); //加入queue中 while (myq.size()>0) { nowp = myq.top(); //取出queue的第一個 myq.pop(); //將queue的第一個刪除 for (int k = 0; k<4; k++) { //四個方向加入queue nextp.r = nowp.r + gor[k]; nextp.c = nowp.c + goc[k]; if ((bound(nextp.r, nextp.c, N)) && (t[nextp.r][nextp.c]>t[nowp.r][nowp.c] + map[nextp.r][nextp.c])) { //在地圖內，且發現比較小 t[nextp.r][nextp.c] = t[nowp.r][nowp.c] + map[nextp.r][nextp.c]; if (nextp.r == i && nextp.c == j) { while (myq.size() > 0) { myq.pop(); } break; } myp.r = nextp.r; myp.c = nextp.c; myp.w = t[myp.r][myp.c]; myq.push(myp); //加入queue } } } map[i][j] = tmp; ans[r][c][i][j] = t[i][j]; } int main() { int N, q, r0, c0, r1, c1, min, max, result; Point myp, nextp; while (scanf("%d", &N) != EOF) { min = 1001; max = 0; memset(ans,-1,sizeof(ans)); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { scanf("%d", &map[i][j]); if (min>map[i][j]) min = map[i][j]; if (max<map[i][j]) max = map[i][j]; } } scanf("%d", &q); for (int i = 0; i<q; i++) { scanf("%d %d %d %d", &r0, &c0, &r1, &c1); if (min == max) printf("%d\n", abso(r0, r1)*min + abso(c0, c1)*min);//地圖每一個點值相同 else{ result = 1000000; for (int i = 1; i<=N; i++) {//要在(i,j)使用死光彈 for (int j = 1; j<=N; j++) { //if (map[i][j] != min) { //有可能起點到終點的長方形區塊都是min if (ans[r0][c0][i][j] == -1) bfs0(r0, c0, i, j, N); if (ans[r1][c1][i][j] == -1) bfs1(r1, c1, i, j, N); if (result > (ans[r0][c0][i][j] + ans[r1][c1][i][j])) result = ans[r0][c0][i][j] + ans[r1][c1][i][j]; //} } } printf("%d\n", result); } } } return 0; }