1 /*======================================================================
2 * Author : kevin
3 * Filename : FindingNemo.cpp
4 * Creat time : 2014-05-26 20:27
5 * Description :
6 ========================================================================*/
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #define clr(a,b) memset(a,b,sizeof(a))
14 #define M 205
15 #define INF 0x7f7f7f7f
16 using namespace std;
17 int d[M][M][4],s[M][M][2];
18 int vis[M][M],cnt[M][M];
19 int lastx,lasty,maxx,maxy;
20 int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
21 struct Node //优先队列，按cnt统计的步数排序
22 {
23 int x,y;
24 bool operator <(const Node &a) const{
25 return cnt[a.x][a.y] < cnt[x][y];
26 }
27 }node;
28 void BFS()
29 {
30 priority_queueque;
31 Node temp;
32 node.x = lastx; node.y = lasty;
33 que.push(node);
34 vis[lastx][lasty] = 1;
35 while(que.empty() != true){
36 int x,y;
37 temp = que.top();
38 que.pop();
39 for(int i = 0; i <4; i++){
40 x = temp.x + dir[i][0]; y = temp.y + dir[i][1];
41 if(x <0 || y <0) continue;
42 if(x > 199 || y > 199) continue;
43 if(d[x][y][3-i] != 1){ //若不是墙
44 node.x = x; node.y = y;
45 if(d[x][y][3-i] == 0){ //若是门
46 if(vis[x][y]) //若被访问过，更新cnt值
47 cnt[x][y] = min(cnt[x][y],cnt[temp.x][temp.y]+1);
48 else{
49 cnt[x][y] = cnt[temp.x][temp.y]+1;
50 que.push(node);
51 }
52 }
53 else{ //若是空地
54 if(vis[x][y])//若被访问过，更新cnt值
55 cnt[x][y] = min(cnt[x][y],cnt[temp.x][temp.y]);
56 else{
57 cnt[x][y] = cnt[temp.x][temp.y];
58 que.push(node);
59 }
60 }
61 vis[x][y] = 1; //访问标记
62 if(x > maxx || y > maxy){ //达到边界，将步数更新到cnt[0][0]
63 cnt[0][0] = min(cnt[0][0],cnt[x][y]);
64 break;
65 }
66 }
67 }
68 }
69 }
70 void BuildGrap() //建图
71 {
72 for(int i = 0; i <200; i++){
73 for(int j = 0; j <200; j++){
74 d[i][j][0] = s[i][j+1][0];
75 d[i][j][1] = s[i+1][j][1];
76 d[i][j][3] = s[i][j][0];
77 d[i][j][2] = s[i][j][1];
78
79 }
80 }
81 }
82 int main(int argc,char *argv[])
83 {
84 int n,m,a,b,dd,t;
85 double xx,yy;
86 while(scanf("%d%d",&n,&m)!=EOF){
87 clr(d,-1);
88 clr(s,-1);
89 clr(vis,0);
90 clr(cnt,0);
91 if(n == -1 && m == -1) break;
92 maxx = maxy = 0;
93 for(int i = 0; i ){
94 scanf("%d%d%d%d",&a,&b,&dd,&t);
95 if(dd == 1){
96 for(int k = 0; k ){
97 s[a][b][dd] = 1;
98 b++;
99 }
100 }
101 if(dd == 0){
102 for(int k = 0; k ){
103 s[a][b][dd] = 1;
104 a++;
105 }
106 }
107 if(maxx < a){
108 maxx = a;
109 }
110 if(maxy < b){
111 maxy = b;
112 }
113 }
114 for(int i = 0; i ){
115 scanf("%d%d%d",&a,&b,&dd);
116 s[a][b][dd] = 0;
117 }
118 scanf("%lf%lf",&xx,&yy);
119 lastx = floor(xx);
120 lasty = floor(yy);
121 if(lastx <0 || lastx > 199 || lasty <0 || lasty > 199){
122 printf("0\n");
123 continue;
124 }
125 BuildGrap();
126 cnt[0][0] = INF;
127 BFS();
128 if(cnt[0][0] == INF){
129 printf("-1\n");
130 }
131 else{
132 printf("%d\n",cnt[0][0]);
133 }
134 }
135 return 0;
136 }
京公网安备 11010802041100号