2 solutions

  • 0
    @ 2024-9-18 17:29:43
    #include <iostream>
    #include <queue>
    #include <vector>
    #include <climits>
    
    using namespace std;
    
    int main() {
        int N, A, B;
        cin >> N >> A >> B;
        vector<int> K(N + 1);
        for (int i = 1; i <= N; ++i) {
            cin >> K[i];
        }
    
        // 记录每层是否已访问
        vector<bool> visited(N + 1, false);
        // 队列存储当前层和到达该层的按键次数
        queue<pair<int, int>> q;
        q.push({A, 0});
        visited[A] = true;
    
        while (!q.empty()) {
            int current_floor = q.front().first;
            int steps = q.front().second;
            q.pop();
    
            if (current_floor == B) {
                cout << steps << endl;
                return 0;
            }
            // 尝试上楼
            int next_floor_up = current_floor + K[current_floor];
            if (next_floor_up <= N && !visited[next_floor_up]) {
                visited[next_floor_up] = true;
                q.push({next_floor_up, steps + 1});
            }
            // 尝试下楼
            int next_floor_down = current_floor - K[current_floor];
            if (next_floor_down >= 1 && !visited[next_floor_down]) {
                visited[next_floor_down] = true;
                q.push({next_floor_down, steps + 1});
            }
        }
        cout << -1 << endl;
        return 0;
    }
    
    • 0
      @ 2023-3-5 14:48:36
      #include <iostream>
      using namespace std;
      int w[20003];
      int n,a,b;
      int minn=0x7ffffff;
      bool ans[2003];
      bool check(int x){
      	return (x<=n&&x>=1);
      }
      void dfs(int now,int sum){
      	if(now==b) minn=min(minn,sum);
          if(sum>minn) return;
      	ans[now]=1;
      	if(check(now+w[now])&&(!ans[now+w[now]]))
      		dfs(now+w[now],sum+1);
      	if(check(now-w[now])&&(!ans[now-w[now]]))
      		dfs(now-w[now],sum+1);
      	ans[now]=0;
          return ;
      }
      int main(){
      	cin>>n>>a>>b;
      	for(int i=1;i<=n;i++){
      		cin>>w[i];
      	}
      	dfs(a,0);
      	if(minn!=0x7ffffff) cout<<minn;
      	else cout<<-1;
      	return 0;
      }
      • 1

      Information

      ID
      6705
      Time
      1000ms
      Memory
      256MiB
      Difficulty
      9
      Tags
      (None)
      # Submissions
      83
      Accepted
      9
      Uploaded By