Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
SPFA,WA我N次,终于过了,INF要设置大点,也不能太大//SPFA求网格最短路问题 #define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<queue> #include<algorithm> using namespace std; const int MAXN = 201; #define INF MAXN*MAXN int W[MAXN][MAXN], H[MAXN][MAXN]; int dis[MAXN][MAXN]; int maxX, maxY; struct Point{ int x, y; Point(int x = 0, int y = 0){ this->x = x; this->y = y; } }; bool isLeg(int x, int y){ return x > -1 && y > -1 && x <=maxX&&y <=maxY; } void SPFA(){ //SPFA queue<Point>Q; Point next, now; Q.push(Point(0,0)); for (int i = 0; i < MAXN;i++) for (int j = 0; j < MAXN; j++) dis[i][j] = INF; dis[0][0] = 0; while (!Q.empty()){ now = Q.front(); Q.pop(); int x = now.x,y = now.y; /*接下来进行松弛操作*/ //检查左边网格 if (isLeg(x - 1, y) && dis[x - 1][y] > dis[x][y] + W[x][y]){ dis[x - 1][y] = dis[x][y] + W[x][y]; Q.push(Point(x-1,y)); //入队 } //检查右边网格 if (isLeg(x+1, y) && dis[x+1][y] > dis[x][y] + W[x+1][y]){ dis[x +1][y] = dis[x][y] + W[x+1][y]; Q.push(Point(x +1, y)); //入队 } //检查上方网格 if (isLeg(x, y+1) && dis[x][y+1] > dis[x][y] + H[x][y+1]){ dis[x][y+1] = dis[x][y] + H[x][y+1]; Q.push(Point(x, y+1)); //入队 } //检查下方网格 if (isLeg(x, y-1) && dis[x][y-1] > dis[x][y] + H[x][y]){ dis[x][y-1] = dis[x][y] + H[x][y]; Q.push(Point(x, y-1)); //入队 } } } int main(){ int m, n, i, j,x,y,d,t; while (scanf("%d%d", &n, &m) && n != -1){ memset(W, 0, sizeof(W)); memset(H, 0, sizeof(H)); maxX = maxY = 0; for (i = 0; i < n; i++){ scanf("%d%d%d%d", &x, &y, &d, &t); if (d){ //y轴平行 maxX = max(x, maxX); maxY = max(y+t, maxY); for (j = 0; j < t; j++) W[x][y + j] =INF; //设置为无穷 } else{ maxX = max(x+t, maxX); maxY = max(y, maxY); for (j = 0; j < t; j++) H[x + j][y] =INF; } } for (i = 0; i < m; i++){ scanf("%d%d%d", &x, &y, &d); if (d) W[x][y] = 1; else H[x][y] = 1; } double fx, fy; cin >> fx >>fy;//scanf("%lf%lf", &fx, &fy); //Nemo的位置 x = int(fx), y = int(fy); if (x > maxX || y > maxY) //在迷宫外面 printf("0\n"); else{ SPFA(); if (dis[x][y]>=INF) printf("-1\n"); else printf("%d\n", dis[x][y]); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator