时间限制: 1500 ms 空间限制: 524288 KB
题目描述
输入
输出
样例输入
1
2
3
4
5
6
7
8
9
10
| 样例输入1
2 2
+*
*U
1 1 2 2
样例输入2
2 3
<><
><>
1 1 2 1
|
样例输出
数据范围限制
提示
题目标中的特殊符号：<>^v+*|-
代码
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
| #include<bits/stdc++.h>
using namespace std;
struct way
{
bool up[1010][1010];
bool left[1010][1010];
bool right[1010][1010];
bool down[1010][1010];
}a[4];
int n,m,f[4000100],x1,y2,x2,y3,b[4000100][3],d[4000100],next[4]={1,2,3,0};
bool sf[1010][1010][4];
char a1[1010][1010];
void bfs()
{
int head=0,tail=1,x,y,z,nx,ny,nz;
b[1][0]=x1;
b[1][1]=y2;
b[1][2]=0;
while(head<tail)
{
head++;
x=b[head][0];
y=b[head][1];
z=b[head][2];
if(x==x2 && y==y3)
{
cout<<f[head];
return;
}
if(x+1<=n)
{
if(a[z].down[x][y]==1 && a[z].up[x+1][y]==1 && sf[x+1][y][z]==0)
{
tail++;
b[tail][0]=x+1;
b[tail][1]=y;
b[tail][2]=z;
f[tail]=f[head]+1;
sf[x+1][y][z]=1;
}
}
if(x-1>=1)
{
if(a[z].down[x-1][y]==1 && a[z].up[x][y]==1 && sf[x-1][y][z]==0)
{
tail++;
b[tail][0]=x-1;
b[tail][1]=y;
b[tail][2]=z;
f[tail]=f[head]+1;
sf[x-1][y][z]=1;
}
}
if(y+1<=m)
{
if(a[z].right[x][y]==1 && a[z].left[x][y+1]==1 && sf[x][y+1][z]==0)
{
tail++;
b[tail][0]=x;
b[tail][1]=y+1;
b[tail][2]=z;
f[tail]=f[head]+1;
sf[x][y+1][z]=1;
}
}
if(y-1>=1)
{
if(a[z].right[x][y-1]==1 && a[z].left[x][y]==1 && sf[x][y-1][z]==0)
{
tail++;
b[tail][0]=x;
b[tail][1]=y-1;
b[tail][2]=z;
f[tail]=f[head]+1;
sf[x][y-1][z]=1;
}
}
if(sf[x][y][next[z]]==0)
{
tail++;
b[tail][0]=x;
b[tail][1]=y;
b[tail][2]=next[z];
f[tail]=f[head]+1;
sf[x][y][next[z]]=1;
}
}
cout<<-1;
}
int main()
{
freopen("temple.in","r",stdin);
freopen("temple.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a1[i][j];
if(a1[i][j]=='+') {a[0].down[i][j]=1;a[0].left[i][j]=1;a[0].right[i][j]=1;a[0].up[i][j]=1;}
else if(a1[i][j]=='-'){a[0].down[i][j]=0;a[0].left[i][j]=1;a[0].right[i][j]=1;a[0].up[i][j]=0;}
else if(a1[i][j]=='|'){a[0].down[i][j]=1;a[0].left[i][j]=0;a[0].right[i][j]=0;a[0].up[i][j]=1;}
else if(a1[i][j]=='^'){a[0].down[i][j]=0;a[0].left[i][j]=0;a[0].right[i][j]=0;a[0].up[i][j]=1;}
else if(a1[i][j]=='>'){a[0].down[i][j]=0;a[0].left[i][j]=0;a[0].right[i][j]=1;a[0].up[i][j]=0;}
else if(a1[i][j]=='<'){a[0].down[i][j]=0;a[0].left[i][j]=1;a[0].right[i][j]=0;a[0].up[i][j]=0;}
else if(a1[i][j]=='v'){a[0].down[i][j]=1;a[0].left[i][j]=0;a[0].right[i][j]=0;a[0].up[i][j]=0;}
else if(a1[i][j]=='L'){a[0].down[i][j]=1;a[0].left[i][j]=0;a[0].right[i][j]=1;a[0].up[i][j]=1;}
else if(a1[i][j]=='R'){a[0].down[i][j]=1;a[0].left[i][j]=1;a[0].right[i][j]=0;a[0].up[i][j]=1;}
else if(a1[i][j]=='U'){a[0].down[i][j]=1;a[0].left[i][j]=1;a[0].right[i][j]=1;a[0].up[i][j]=0;}
else if(a1[i][j]=='D'){a[0].down[i][j]=0;a[0].left[i][j]=1;a[0].right[i][j]=1;a[0].up[i][j]=1;}
else if(a1[i][j]=='*'){a[0].down[i][j]=0;a[0].left[i][j]=0;a[0].right[i][j]=0;a[0].up[i][j]=0;}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
for(int l=1;l<=3;l++)
{
if(a[l-1].down[i][j]) a[l].left[i][j]=1;
else a[l].left[i][j]=0;
if(a[l-1].left[i][j]) a[l].up[i][j]=1;
else a[l].up[i][j]=0;
if(a[l-1].right[i][j]) a[l].down[i][j]=1;
else a[l].down[i][j]=0;
if(a[l-1].up[i][j]) a[l].right[i][j]=1;
else a[l].right[i][j]=0;
}
}
cin>>x1>>y2>>x2>>y3;
bfs();
return 0;
}
|
微信
支付宝
