1043 - Crossing Streets

发布时间:2016-12-11 6:46:04 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"1043 - Crossing Streets",主要涉及到1043 - Crossing Streets方面的内容,对于1043 - Crossing Streets感兴趣的同学可以参考一下。

Peter Longfoot is a student at the university of Suburbia. Every morning, Peter leaves home to walk to the university. Many other students are driving their cars or riding their bicycles to campus, but Peter prefers to walk, avoiding the chaotic traffic of the city as much as possible. Unfortunately, Peter cannot avoid the traffic entirely, since he has to cross streets in order to reach the university. Recently, Peter has wondered how to minimize the number of streets he has to cross. For example, in the following map, streets are drawn as horizontal and vertical lines. To reach the university starting at his home, Peter has to cross at least two streets. Peter cannot cross a street pair at an intersection and Peter cannot walk along a street. Figure: Streets are shown as straight lines and the arrows show possible walking paths for Peter. The black arrows show one possible path for Peter where he only has to cross two streets. The gray arrows show a path for Peter where he needs to cross four streets. The path shown by the dotted arrows is not legal because it crosses two streets at an intersection. The figure above corresponds to the first sample input. Peter knows the locations of all streets in the city, but he has trouble figuring out the best way to the university. So you must write a program to help him. Input  The input consists of several descriptions of cities. Each description starts with a line containing a single integer n (1n500), the number of streets in the city. This is followed by n lines, each containing four integers x1, y1, x2, y2, indicating that there is a street from coordinates (x1, y1) to (x2,y2). All streets are parallel to either the x- or y-axis, since the city is built on a square grid. Streets can overlap, in which case they are counted as only one street. The city description is concluded by a line containing four integers xh, yh, xu, yu, the coordinates (xh, yh) of Peter's home, and the coordinates (xu,yu) of the university, respectively. Neither Peter's home nor the university will be located on a street. You should consider the streets as straight-line segments, so the streets have no width. Although the endpoints of the streets are integers, Peter doesn't need to walk along the grids. He can walk in any direction he likes. The magnitudes of all integers in the input file are less than 2×109. The input is terminated by a line consisting of the integer zero. Output  For each city description, first output its number in the sequence of descriptions. Then output the minimum number of streets that Peter has to cross to go from his home to the university. Follow the format of the sample output. Sample Input  8 6 0 24 0 24 0 24 4 24 4 6 4 6 4 6 0 12 1 26 1 26 1 26 6 26 6 12 6 12 6 12 1 0 1 17 3 1 10 10 20 10 1 1 30 30 0 Sample Output  City 1 Peter has to cross 2 streets City 2 Peter has to cross 0 streets #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; const int MaxS=500; const int MaxN=500*2+4; const int add[4][2]={0,1,0,-1,-1,0,1,0}; int City,xh,yh,xu,yu,n,N,q1,q2,q3,ans,i; int coor[2][MaxS*2+4]; int w[MaxS*2+4][MaxS*2+4]; int list[MaxN*MaxN][2]; int map[MaxN][MaxN]; int find(int type,int T) { int l,r,m; l=0;r=n+n+1; while(l!=r) { m=(l+r)/2; if(coor[type][m]<T) l=m+1; else r=m; } return l; } bool init() { int i,j,k,tmp; int streets[MaxS][4]; scanf("%d",&n); if(n==0) return false; for(i=0;i<n;i++) { for(j=0;j<4;j++) scanf("%d",&streets[i][j]); coor[0][i]=streets[i][0]; coor[1][i]=streets[i][1]; coor[0][i+n]=streets[i][2]; coor[1][i+n]=streets[i][3]; } scanf("%d %d %d %d",&xh,&yh,&xu,&yu); coor[0][n+n]=xh; coor[1][n+n]=yh; coor[0][n+n+1]=xu; coor[1][n+n+1]=yu; sort(coor[0],coor[0]+n+n+2); sort(coor[1],coor[1]+n+n+2); for(i=0;i<n;i++) { if(streets[i][0]<streets[i][2]) { tmp=find(0,streets[i][0])+1; streets[i][2]=find(0,streets[i][2])+1; streets[i][0]=tmp; } else { tmp=find(0,streets[i][2])+1; streets[i][2]=find(0,streets[i][0])+1; streets[i][0]=tmp; } if(streets[i][1]<streets[i][3]) { tmp=find(1,streets[i][1])+1; streets[i][3]=find(1,streets[i][3])+1; streets[i][1]=tmp; } else { tmp=find(1,streets[i][3])+1; streets[i][3]=find(1,streets[i][1])+1; streets[i][1]=tmp; } } xh=find(0,xh)+1;yh=find(1,yh)+1; xu=find(0,xu)+1;yu=find(1,yu)+1; N=n+n+3; memset(map,0,sizeof(map)); for(i=0;i<n;i++) if(streets[i][0]==streets[i][2]) { for(j=streets[i][1];j<streets[i][3];j++) { map[streets[i][0]][j] |=4; map[streets[i][0]-1][j] |=8; } } else { for(j=streets[i][0];j<streets[i][2];j++) { map[j][streets[i][1]] |=2; map[j][streets[i][1]-1] |=1; } } return true; } void go(int x,int y,int t) { int i,h,l; for(i=0;i<4;i++) if(!(map[x][y]&(1<<i)) || t) { h=x+add[i][0];l=y+add[i][1]; if(h<0||l<0||h>N||l>N||w[h][l]) continue; w[h][l]=1; list[q3][0]=h;list[q3][1]=l; q3++; if(map[x][y] & (1<<i)) go(h,l,t-1); else go(h,l,t); } } int main() { City=0; while(init()) { memset(w,0,sizeof(w)); w[xh][yh]=1; list[0][0]=xh;list[0][1]=yh; q3=1;go(xh,yh,0); q1=0;q2=q3; ans=0; while(1) { if(w[xu][yu]) break; for(i=q1;i<q2;i++) go(list[i][0],list[i][1],1); ans++; q1=q2;q2=q3; } printf("City %d\n",++City); printf("Peter has to cross %d streets\n",ans); } return 0; }

上一篇:AJAX应用--基于HTML,以GET或POST方式,检查注册用户名是否存在
下一篇:1044 - Tiling the Plane

相关文章

相关评论