fork download 
  1.  
  2.  
  3.  
  4. /* package whatever; // don't place package name! */
  5.  
  6.  
  7. // You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style startingfrom the bottom left of the board
  8. // (i.e. board[n - 1][0]) and alternating direction each row.
  9. // You start on square 1 of the board. In each move, starting from square curr, do the following:
  10. // Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].
  11. // This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
  12. // If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
  13. // The game ends when you reach the square n2.
  14. // A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 do not have a snake or ladder.
  15. // Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.
  16. // For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.
  17. // Return the least number of moves required to reach the square n2. If it is not possible to reach the square, return -1
  18. // [-1,-1,-1,-1,-1,-1]
  19. // [-1,-1,-1,-1,-1,-1]
  20. // [-1,-1,-1,-1,-1,-1]
  21. // [-1,35,-1,-1,13,-1]
  22. // [-1,-1,-1,-1,-1,-1]
  23. // [-1,15,-1,-1,-1,-1]
  24. // output: 4
  25. // Explanation:
  26. // In the beginning, you start at square 1 (at row 5, column 0).
  27. // You decide to move to square 2 and must take the ladder to square 15.
  28. // You then decide to move to square 17 and must take the snake to square 13.
  29. // You then decide to move to square 14 and must take the ladder to square 35.
  30. // You then decide to move to square 36, ending the game.
  31. // This is the lowest possible number of moves to reach the last square, so return 4.
  32. //
  33.  
  34. // -1 -1 -1
  35. // -1 -1 -1
  36. // -1 -1 -1
  37.  
  38.  
  39. #include<bits/stdc++.h>
  40. using namespace std;
  41.  
  42. bool vis[100001];
  43. map<int,int> dp;
  44. int dfs(vector<vector<pair<int,int> > > &v,int i,int n) {
  45. 	// int n=v.size()-1;
  46. 	// cout<<n;
  47. 	if(dp[i]!=0) return dp[i];
  48. 	if(vis[i]) return -1;
  49. 	if(i>=n*n) return 0;
  50. 	vis[i]=true;
  51. 	int res = n*n+1;
  52. 	for(int j=0;j<v[i].size();j++) {
  53. 		if(!vis[v[i][j].first]) {
  54. 			int val = dfs(v,v[i][j].first,n);
  55. 			if(val!=-1){
  56. 				res = min(res,v[i][j].second+val);
  57. 			}
  58. 		}
  59. 	}
  60. 	vis[i]=false;
  61. 	if(res == n*n) {
  62. 		dp[i]=-1;
  63. 		return -1;
  64. 	}
  65. 	dp[i]=res;
  66. 	return res;
  67. }
  68. int main() {
  69. 	int n;
  70. 	cin>>n;
  71. 	memset(vis,false,sizeof(vis));
  72. 	vector<vector<pair<int,int> > > v(n*n+1);
  73.  
  74. 	int m;
  75. 	cin>>m;
  76. 	for(int i=0;i<m;i++) {
  77. 		int x,y;
  78. 		cin>>x>>y;
  79. 		v[x].push_back({y,0});
  80. 		v[y].push_back({x,0});
  81. 	}
  82. 	for(int i=1;i<=n*n;i++) {
  83. 		for(int j=i+1;j<=min(i+6,n*n);j++) {
  84. 			v[i].push_back({j,1});
  85. 		}
  86. 	}
  87.  
  88. 	int res = dfs(v,1,n);
  89. 	cout<<res<<"\n";
  90. 	return 0;
  91. }
  92.  
  93.  
  94.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin 
6
3
2 15
14 13
17 35
stdout 
3
https://ideone.com/wzQij5
language:
C++14 (gcc 8.3)
created:
1 day 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!