fork download 
  1. /**
  2.  *    author:  orzvanh14 ( Độc cô cầu đặc )
  3.  *    created: 23.12.2022 10:08:02
  4.  *    too lazy to update time
  5. **/
  6. // i wants to take ioi
  7. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #define nn "\n"
  14. #define pi pair<int, int>
  15. #define fi first
  16. #define se second
  17. #define lb lower_bound
  18. #define ub upper_bound
  19. #define eb emplace_back
  20. #define pb push_back
  21. #define TASK " "
  22.  
  23. #define ms(a, x) memset(a, x, sizeof(a))
  24. #define all(a) a.begin(), a.end()
  25. #define All(a, n) a + 1, a + 1 + n
  26.  
  27. #define LOG 19
  28.  
  29.  
  30. const int INF = 1e18;
  31. const int mod = 1e9+7;
  32. const int N = 500  + 5;
  33. int MOD = 998244353;
  34. int bit[200000];
  35. int r, c, t;
  36. char a[N][N];
  37. int sr = -1, sc, st, er, ec;
  38. int d[N][N][4];
  39. bool vis[N][N][4];
  40. int sx[] = {0, 0, 1, -1};
  41. int sy[] = {1, -1, 0, 0};
  42. bool oki(int x, int y) {
  43.     return (x >= 1 && x <= r && y >= 1 && y <= c && a[x][y] != '#');
  44. }
  45. bool ok(int x, int y, int st) {
  46.     if(st == 0) return oki(x, y) && a[x][y] != 'E';
  47.     if(st == 1) return oki(x, y) && oki(x, y - 1);
  48.     if(st == 2) return oki(x, y) && oki(x - 1, y);
  49.     return false;
  50. }
  51. void nhap(){
  52.  
  53. }
  54.  
  55. void bfs(){
  56.  
  57. 		if(r == 0 && c == 0) return;
  58. 		int sr = -1;
  59. 		queue<tuple<int, int, int>> q;
  60. 		for(int i = 1; i <= r; i++){
  61. 			for(int j = 1; j <= c; j++){
  62. 				cin >> a[i][j];
  63. 				for(int k = 0; k < 3; k++){
  64.                 	vis[i][j][k] = false;
  65.                 	d[i][j][k] = 0;
  66.             	}
  67. 				if(a[i][j] == 'X'){
  68.                 	if(sr == -1){
  69.                     	sr = i; sc = j; st = 0;
  70.                 	}
  71.                 	else{
  72.                     	if(i == sr) st = 1; 
  73.                     	else st = 2; 
  74.                     	sr = i; sc = j;
  75.                 	}
  76.             	} 
  77.             	else if(a[i][j] == 'O'){
  78.                 	er = i; ec = j;
  79.             	}
  80. 			}
  81. 		}
  82. 		q.push({sr, sc, st});
  83. 		vis[sr][sc][st] = true;
  84. 	    d[sr][sc][st] = 0;
  85. 	    while(!q.empty()){
  86.         	auto [x, y, tt] = q.front(); q.pop();
  87.         	if(tt == 0 && x == er && y == ec){
  88.             	cout << d[x][y][tt] << nn;
  89.             	return;
  90.         	}
  91.         	int cx, cy, cst;
  92.         	for(int i = 0; i < 4; i++){
  93.             	if(tt == 0){ 
  94.                 	if(i == 0){ 
  95.                 		cx = x; cy = y - 1; cst = 1; 
  96.                 	}
  97.                 	else if(i == 1){ 
  98.                 		cx = x; cy = y + 2; cst = 1; 
  99.                 	}
  100.                 	else if(i == 2){ 
  101.                 		cx = x - 1; cy = y; cst = 2;
  102.                 	}
  103.              		else{ 
  104.              			cx = x + 2; cy = y; cst = 2; 
  105.              		}
  106.             	} 
  107.             	else if(tt == 1){ 
  108.                 	if(i == 0){ 
  109.                 		cx = x; cy = y - 2; cst = 0; 
  110.                 	}
  111.                 	else if(i == 1){ 
  112.                 		cx = x; cy = y + 1; cst = 0; 
  113.                 	}
  114.                 	else if(i == 2){ 
  115.                 		cx = x - 1; cy = y; cst = 1; 
  116.                 	}
  117.                 	else{ 
  118.                 		cx = x + 1; cy = y; cst = 1; 
  119.                 	}
  120.             	} 
  121.             	else{ 
  122.                 	if(i == 0){ 
  123.                 		cx = x; cy = y - 1; cst = 2; 
  124.                 	}
  125.                	 	else if(i == 1){ 
  126.                	 		cx = x; cy = y + 1; cst = 2; 
  127.                	 	}
  128.                 	else if(i == 2){ 
  129.                 		cx = x - 2; cy = y; cst = 0; 
  130.                 	}
  131.                 	else{ 
  132.                 		cx = x + 1; cy = y; cst = 0;
  133.                 	}
  134.             	}
  135.             	if(ok(cx, cy, cst) && !vis[cx][cy][cst]){
  136.                 	d[cx][cy][cst] = d[x][y][tt] + 1;
  137.                 	vis[cx][cy][cst] = 1;
  138.                 	q.push({cx, cy, cst});
  139.             	}
  140.         	}
  141.     	}
  142.     	cout << "Impossible" << nn;
  143.  
  144.  
  145. }
  146. signed main() {
  147. 	// freopen("input.txt", "r", stdin);
  148. 	// freopen("output.txt", "w", stdout);
  149. 	ios_base::sync_with_stdio(0);
  150. 	cin.tie(0);
  151. 	cout.tie(0);
  152.     while(cin >> r >> c){
  153.     	bfs();
  154.     }
  155. 	return 0;
  156.  
  157. }
  158.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/gdL9a8
language:
C++14 (gcc 8.3)
created:
22 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!