HDU_2757

? ? 由于邊權只有0和1，可以用稍加變形的BFS，也可以直接用優(yōu)先級隊列，由于后者省事一些，所以就直接用優(yōu)先級隊列來寫了，不過當然效率也會低一些。

#include<stdio.h> #include<string.h> #include<queue> #define MAXD 1010 #define INF 0x3f3f3f3f char b[MAXD]; int N, M, dis[MAXD][MAXD], g[MAXD][MAXD], sx, sy, tx, ty; int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; struct Point {int x, y, dis;Point(){}Point(int _x, int _y, int _dis) : x(_x), y(_y), dis(_dis){}bool operator < (const Point &t) const{return dis > t.dis; } }; void init() {int i, j;for(i = 1; i <= N; i ++){scanf("%s", b + 1);for(j = 1; j <= M; j ++) g[i][j] = b[j] - '0'; } } inline int inside(int x, int y) {return x >= 1 && x <= N && y >= 1 && y <= M; } void dij() {int i, j, x, y, z;std::priority_queue <Point> q;for(i = 1; i <= N; i ++) for(j = 1; j <= M; j ++) dis[i][j] = INF;dis[sx][sy] = 0;q.push(Point(sx, sy, 0));while(!q.empty()){Point p = q.top();q.pop();if(p.x == tx && p.y == ty) break;for(i = 0; i < 8; i ++){x = p.x + dx[i], y = p.y + dy[i];z = p.dis + 1 - (i == g[p.x][p.y]);if(inside(x, y) && z < dis[x][y])dis[x][y] = z, q.push(Point(x, y, z));}}printf("%d\n", dis[tx][ty]); } void solve() {int i, n;scanf("%d", &n);for(i = 0; i < n; i ++){scanf("%d%d%d%d", &sx, &sy, &tx, &ty);dij(); } } int main() {while(scanf("%d%d", &N, &M) == 2){init();solve(); }return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU 2757 Ocean Currents的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。