| ||||||||||
| 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