fork download
copy 
  1. /*
  2. '########:::::'###::::'##::: ##::'######::::'######:::'#######::'########::'########:'########::
  3.  ##.... ##:::'## ##::: ###:: ##:'##... ##::'##... ##:'##.... ##: ##.... ##: ##.....:: ##.... ##:
  4.  ##:::: ##::'##:. ##:: ####: ##: ##:::..::: ##:::..:: ##:::: ##: ##:::: ##: ##::::::: ##:::: ##:
  5.  ##:::: ##:'##:::. ##: ## ## ##: ##::'####: ##::::::: ##:::: ##: ##:::: ##: ######::: ########::
  6.  ##:::: ##: #########: ##. ####: ##::: ##:: ##::::::: ##:::: ##: ##:::: ##: ##...:::: ##.. ##:::
  7.  ##:::: ##: ##.... ##: ##:. ###: ##::: ##:: ##::: ##: ##:::: ##: ##:::: ##: ##::::::: ##::. ##::
  8.  ########:: ##:::: ##: ##::. ##:. ######:::. ######::. #######:: ########:: ########: ##:::. ##:
  9. ........:::..:::::..::..::::..:::......:::::......::::.......:::........:::........::..:::::..::
  10. */
  11. #include<bits/stdc++.h>
  12. using namespace std;
  13. const int inf = 1e9;
  14. const long long linf = 1e18;
  15. int n, m;
  16. int a[1005][1005];
  17. map<tuple<int, int, int>, bool> vis;
  18. using idk = tuple<int,int,int,int>;
  19.  
  20. void solve()
  21. {
  22. 	queue<idk> q;
  23. 	q.push({0, 1, 1, 0});
  24. 	vis[{1, 1, 0}] = true;
  25. 	while(!q.empty())
  26. 	{
  27. 		auto [d, r, c, mask] = q.front();
  28. 		q.pop();
  29. 		if(r == n && m == c)
  30. 		{
  31. 			cout << d;
  32. 			return;
  33. 		}
  34. 		for(int i = 0; i < 8; i++)
  35. 		{
  36. 			if((mask >> i) & 1) continue;
  37. 			int r2 = r + (i == 0 || i == 1 || i == 7 ? a[r][c] : (i == 2 || i == 6 ? 0 : -a[r][c]));
  38. 			int c2 = c + (i == 1 || i == 2 || i == 3 ? a[r][c] : (i == 0 || i == 4 ? 0 : -a[r][c]));
  39. 			if(r2 < 1 || r2 > n || c2 < 1 || c2 > m) continue;
  40. 			int mask2 = mask | (1 << i);
  41. 			if(!vis[{r2, c2, mask2}])
  42. 			{
  43. 				vis[{r2, c2, mask2}] = true;
  44. 				q.push({d + 1, r2, c2, mask2});
  45. 			}
  46. 		}
  47. 	}
  48. 	cout << -1;
  49. }
  50.  
  51. int main()
  52. {
  53. 	ios_base::sync_with_stdio(false);
  54. 	cin.tie(0); cout.tie(0);
  55. 	if(fopen(".INP", "r")) {
  56. 		freopen(".INP", "r", stdin);
  57. 		freopen(".OUT", "w", stdout);
  58. 	}
  59. 	cin >> m >> n;
  60. 	for(int i = 1; i <= n; i++)
  61. 	{
  62. 		for(int j = 1; j <= m; j++)
  63. 		{
  64. 			cin >> a[i][j];
  65. 		}
  66. 	}
  67. 	solve();
  68. 	return 0;
  69. }
  70.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/qPxwts
language:
C++ (gcc 8.3)
created:
5 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!