input:temple.in output:temple.out

时间限制: 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

样例输出

1
2
3
4
样例输出1
-1
样例输出2
4

数据范围限制

提示

题目标中的特殊符号：<>^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;
}