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
stdin
6
3
2 15
14 13
17 35
stdout
3