首页 > 代码库 > codeforces -676D(Theseus and labyrinth)
codeforces -676D(Theseus and labyrinth)
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <bitset> 6 #include <vector> 7 #include <queue> 8 #include <stack> 9 #include <cmath> 10 #include <list> 11 #include <set> 12 #include <map> 13 #define rep(i,a,b) for(int i = a;i <= b;++ i) 14 #define per(i,a,b) for(int i = a;i >= b;-- i) 15 #define mem(a,b) memset((a),(b),sizeof((a))) 16 #define FIN freopen("in.txt","r",stdin) 17 #define FOUT freopen("out.txt","w",stdout) 18 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 19 #define mid ((l+r)>>1) 20 #define ls (id<<1) 21 #define rs ((id<<1)|1) 22 #define INF 0x3f3f3f3f 23 using namespace std; 24 typedef long long LL; 25 typedef pair<int, int> PIR; 26 const int N = 1e3+5; 27 28 int n, m, xs, ys, xe, ye, G[N][N], dir[4][2] = {0,-1,1,0,0,1,-1,0}; 29 bool vis[N][N][10]; 30 string s; 31 struct Node{ 32 int x, y, cnt, turn; 33 Node (int _x, int _y, int _cnt, int _turn){ 34 x = _x; y = _y; cnt = _cnt; turn = _turn; 35 } 36 }; 37 inline int get(char c){ 38 if(c == ‘+‘) return 15; 39 if(c == ‘-‘) return 5; 40 if(c == ‘|‘) return 10; 41 if(c == ‘^‘) return 8; 42 if(c == ‘>‘) return 4; 43 if(c == ‘<‘) return 1; 44 if(c == ‘v‘) return 2; 45 if(c == ‘L‘) return 14; 46 if(c == ‘R‘) return 11; 47 if(c == ‘U‘) return 7; 48 if(c == ‘D‘) return 13; 49 if(c == ‘*‘) return 0; 50 } 51 bool judge(int x, int y, int stu){ 52 if(x < 1 || x > n || y < 1 || y > m || vis[x][y][stu] || !G[x][y]) return false; 53 return true; 54 } 55 void bfs(){ 56 queue <Node> Q; 57 mem(vis, false); 58 Q.push(Node(xs, ys, 0, 0)); 59 vis[xs][ys][0] = true; 60 while(!Q.empty()){ 61 Node h = Q.front(); 62 Q.pop(); 63 64 int xx = h.x, yy = h.y, cntt = h.cnt, turnn = h.turn; 65 if(xx == xe && yy == ye){ 66 cout << cntt << endl; 67 return ; 68 } 69 if(!vis[xx][yy][(turnn+1)%4]){ 70 Q.push(Node(xx, yy, cntt+1, (turnn+1)%4)); 71 vis[xx][yy][(turnn+1)%4] = true; 72 } 73 rep(i, 0, 3){ 74 int xi = xx+dir[i][0], yi = yy+dir[i][1]; 75 if(judge(xi, yi, turnn) && (G[xx][yy]&(1<<(i+turnn)%4)) && (G[xi][yi]&(1<<(i+turnn+2)%4))){ 76 Q.push(Node(xi, yi, cntt+1, turnn)); 77 vis[xi][yi][turnn] = true; 78 } 79 } 80 } 81 cout << -1 << endl; 82 return ; 83 } 84 int main() 85 {IO; 86 cin >> n >> m; 87 rep(i, 1, n){ 88 cin >> s; 89 rep(j, 0, m-1) G[i][j+1] = get(s[j]); 90 } 91 cin >> xs >> ys; 92 cin >> xe >> ye; 93 bfs(); 94 return 0; 95 }
codeforces -676D(Theseus and labyrinth)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。