fork download 
  1. #include<stdio.h>
  2. #include<deque>
  3.  
  4. using namespace std;
  5. int dx[4] = { 0,-1,0, 1};
  6. int dy[4] = { 1,0,-1, 0};
  7. char M[22][22];
  8. bool is_gone[22][22][4][22][22][4];
  9. deque<int>quex1, quey1, qued1;
  10. deque<int>quex2, quey2, qued2;
  11. deque<int>quedist;
  12. void push_(int x1, int y1, int d1, int x2, int y2, int d2,int dist) {
  13. 	if (is_gone[x1][y1][d1][x2][y2][d2])return;
  14. 	quex1.push_back(x1);quey1.push_back(y1);qued1.push_back(d1);
  15. 	quex2.push_back(x2);quey2.push_back(y2);qued2.push_back(d2);
  16. 	quedist.push_back(dist);
  17. 	is_gone[x1][y1][d1][x2][y2][d2] = 1;
  18. }
  19.  
  20. int main() {
  21. 	int n;
  22. 	int i, j;
  23. 	scanf("%d", &n);
  24. 	for (i = 0; i < n; i++) {
  25. 		for (j = 0; j < n; j++) {
  26. 			scanf(" %c", &M[i][j]);
  27. 		}
  28. 	}
  29. 	push_(n - 1, 0, 0, n - 1, 0, 1, 0);
  30. 	while (!quex1.empty()) {
  31. 		int x1 = quex1.front(), y1 = quey1.front(), d1 = qued1.front();
  32. 		int x2 = quex2.front(), y2 = quey2.front(), d2 = qued2.front();
  33. 		int dist = quedist.front();
  34. 		if (x1 ==0 && y1 == n - 1 && x2 ==0 && y2 == n - 1) {
  35. 			printf("%d", dist);
  36. 			return 0;
  37. 		}
  38. 		quex1.pop_front(); quey1.pop_front(); qued1.pop_front();
  39. 		quex2.pop_front(); quey2.pop_front(); qued2.pop_front();
  40. 		quedist.pop_front();
  41. 		int nextx1 = x1, nexty1 = y1, nextd1 = d1;
  42. 		int nextx2 = x2, nexty2 = y2, nextd2 = d2;
  43. 		if ((!(x1==0&&y1==n-1))&&0 <= x1 + dx[d1] && x1 + dx[d1] < n && 0 <= y1 + dy[d1] && y1 + dy[d1] < n&&M[x1 + dx[d1]][y1 + dy[d1]] == 'E')nextx1 = x1 + dx[d1], nexty1 = y1 + dy[d1];
  44. 		if ((!(x2==0&&y2==n-1))&&0 <= x2 + dx[d2] && x2 + dx[d2] < n && 0 <= y2 + dy[d2] && y2 + dy[d2] < n&&M[x2 + dx[d2]][y2 + dy[d2]] == 'E')nextx2 = x2 + dx[d2], nexty2 = y2 + dy[d2];
  45. 		push_(nextx1, nexty1, nextd1, nextx2, nexty2, nextd2,dist+1);
  46. 		nextx1 = x1, nexty1 = y1, nextd1 = (d1 + 1)%4;
  47. 		nextx2 = x2, nexty2 = y2, nextd2 = (d2 + 1)%4;
  48. 		push_(nextx1, nexty1, nextd1, nextx2, nexty2, nextd2,dist+1);
  49. 		nextx1 = x1, nexty1 = y1, nextd1 = (d1 + 3) % 4;
  50. 		nextx2 = x2, nexty2 = y2, nextd2 = (d2 + 3) % 4;
  51. 		push_(nextx1, nexty1, nextd1, nextx2, nexty2, nextd2,dist+1);
  52. 	}
  53. 	return 0;
  54. }
Time limit exceeded #stdin #stdout 5s 4492KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Fv6gao
language:
C++ (gcc 8.3)
created:
6 years 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!