思路：
将边当作点，这样建墙的时候点的坐标变换成x' = 2*x-1, y' = 2*y-1,t' = 2*t, 建门同理，但是因为门只要开一格就行所以t还是1。nemo的位置变换后是下取整x,y坐标各＋1，
然后 1代表墙，2代表门，4代表nemo。这题坑在nemo的范围不知道，所以不能直接在开的建图的数组里找，我就这样RE了好多次，不在图的范围里的直接可以判断输出0。然后用优先队列存经过的点，按经过的门次数升序排序。
1 #include <iostream>
2 #include <cstdio>
3 #include <queue>
4 #include <vector>
5 #include <cmath>
6 #include <cstring>
7 #include <string>
8 #include <algorithm>
9 using namespace std;
10
11 int arr[500][500], minStep;
12 bool vis[500][500];
13 int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
14 struct node
15 {
16 int x, y,step;
17 node(){
18 x = y = step = 0;
19 }
20 bool operator == (node that){
21 if(that.x == x && that.y == y) return true;
22 return false;
23 }
24 bool operator < (const node &that) const
25 {
26 return step > that.step;
27 }
28 };
29
30 void init()
31 {
32 memset(arr, 0, sizeof(arr));
33 memset(vis, 0, sizeof(vis));
34 minStep = 160000;
35 }
36 void build_wall(int xx, int yy, int dd, int tt)
37 {
38 int x = 2*xx-1, y = 2*yy-1;
39 if(dd)
40 for(int i = y; i <= y+2*tt; i++)
41 arr[x][i] = 1;
42 else
43 for(int i = x; i <= x+2*tt; i++)
44 arr[i][y] = 1;
45 }
46 void door(int xx, int yy, int dd)
47 {
48 int x = 2 * xx -1, y = 2 * yy -1;
49 if(dd) arr[x][y+1] = 2;
50 else arr[x+1][y] = 2;
51 }
52 bool checkBound(int x, int y)
53 {
54 if(x < 0||y < 0||x>400||y>400) return false;
55 return true;
56 }
57 void findNemo()
58 {
59 node nd, nd2;
60 vis[0][0] = 1;
61 priority_queue<node> q;
62 q.push(nd);
63 while(!q.empty()){
64 nd = q.top(); q.pop();
65 for(int i = 0; i < 4; i++) {
66 int x = dir[i][0] + nd.x, y = dir[i][1] + nd.y;
67 if(checkBound(x, y) && arr[x][y] != 1 && !vis[x][y]) {
68 nd2.step = nd.step; nd2.x = x; nd2.y = y;
69 vis[x][y] = 1;
70 if(arr[x][y] == 2) nd2.step++;
71 q.push(nd2);
72 if(arr[x][y] == 4) {
73 vis[x][y] = 0;
74 minStep = nd2.step;
75 return;
76 }
77 }
78 }
79 }
80 }
81 void solve()
82 {
83 int n, m;
84 while(scanf("%d%d", &m, &n) == 2 && n != -1 && m != -1) {
85 init();
86 int x, y, d, t;
87 for(int i = 0; i < m; i++){
88 scanf("%d%d%d%d", &x, &y, &d, &t);
89 build_wall(x, y, d, t);
90 }
91
92 for(int i = 0; i < n; i++){
93 scanf("%d%d%d", &x, &y, &d);
94 door(x, y, d);
95 }
96 double f1, f2;
97 scanf("%lf%lf", &f1, &f2);
98 node nd; nd.x = 2*(int)floor(f1); nd.y = 2*(int)floor(f2);
99 if(checkBound(nd.x, nd.y)){
100 arr[nd.x][nd.y] = 4;
101 findNemo();
102 if(minStep == 160000) printf("-1\n");
103 else printf("%d\n", minStep);
104 }
105 else printf("0\n");
106 }
107 }
108 int main()
109 {
110 solve();
111 return 0;
112 } View Code
转载于:https://www.cnblogs.com/ZiningTang/p/5256143.html