题目在 –>这里<–
思想就是广度优先搜索，但是代码实现的能力还是有待加强。
记录下这道题遇到的一些问题。
先是输入问题，直接把顶点存入图中，然后将不能访问的点(obstacle)设为1,然后将四个方向转化为数字（0北1西2南3东）。
然后就是BFS的实现了，直接套模板不是很方便，很多细节都重写了，但思路还是一致的。队列里存一个结构体表示状态。一个状态有坐标，方向，时间四个变量。然后要GO和TURN，TURN的话巧妙地模4的方法巧妙转化，而GO的话，要在找到下一个状态后，判断是否边界，点是否可行，是否访问过，如果都没问题，则加入队列，然后标记访问。这里同时判断是否到达终点，如果是，直接跳出函数。
记录两次WA的原因：第一，未读清题目，题目中track是两个方块的重合边，是不包括边界的。而我误将边界点认为可达; 第二，未考虑周全，测试数据中有起始点和终止点相同的case，而我没特殊处理WA了。
总结：分析题目要认真，要考虑情况尽可能全，并记录。
最后，贴代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116//From UVA 314
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
// 0
// 1 3
// 2
class Problem{
private:
int n, m;
int startx, starty, endx, endy;
int direction;
int gh[52][52];
bool vis[52][52][4];
struct state{
int x, y, d, step;
};
public:
void Solve(){
while(Read()){
if (startx == endx && starty == endy){
printf("%d\n",0);
}else{
printf("%d\n", BFS(startx,starty,direction,0));
}
}
}
int BFS(int x, int y, int d, int s){
struct state u, v;
queue<struct state> q;
u.x = x;
u.y = y;
u.d = d;
u.step = s;
q.push(u);
while(!q.empty()){
u = q.front();
q.pop();
for (int i=1; i<4; i=i+2){
v = u;
v.d = (v.d + i)%4;
v.step++;
if (!vis[v.x][v.y][v.d]) q.push(v);
vis[v.x][v.y][v.d] = true;
}
for (int i=1; i<4; i++){
v = u;
v.x += i * dx[u.d];
v.y += i * dy[u.d];
v.step++;
if (v.x<=0 || v.y<=0 || v.x>=m || v.y>=n)
continue;//border!!!
if (gh[v.x][v.y] == 1)
break;//careful!!!(not continue)
if (v.x == endx && v.y == endy)
return v.step;
if (!vis[v.x][v.y][v.d]) q.push(v);
vis[v.x][v.y][v.d] = true;
}
}
return -1;
}
bool Read(){
int tmp;
string dirt;
scanf("%d%d", &m, &n);
if (n==0 && m==0) return false;
Init();
for (int i=0; i<m; i++){
for (int j=0; j<n; j++){
cin >> tmp;
if (tmp){
gh[i][j] = gh[i+1][j] = 1;
gh[i][j+1] = gh[i+1][j+1] = 1;
}
}
}
scanf("%d%d%d%d", &startx, &starty, &endx, &endy);
cin >> dirt;
if (dirt == "north"){
direction = 0;
}else if (dirt == "west"){
direction = 1;
}else if (dirt == "south"){
direction = 2;
}else if (dirt == "east"){
direction = 3;
}
return true;
}
void Init(){
memset(gh, 0, sizeof(gh));
memset(vis, 0, sizeof(vis));
}
};
int main(){
Problem ro;
ro.Solve();
}