Informatics Orsay all in one 1360: strange lift

【 Topic link 】

ybt 1360： Strange elevator (lift)
Luogu P1135 Strange elevator

【 Topic test site 】

1. Guang Shu

【 Their thinking 】

remember k[i] For the first time i The number marked on the floor .
This problem is similar to the problem of finding the shortest path in a maze , This problem can be solved by extensive search .
Let the node contain the number of floors x And the number of keystrokes s, First let the starting floor a And the number of keystrokes 0 The team . One node per team u, At this time, on the floor u.x, The next accessible floor is u.x+k[u.x] And u.x-k[u.x], As long as this floor exists , And I haven't visited , Then the number of floors of the new node is the next possible floor , The number of keystrokes of the new node is added to the number of keystrokes of the original node 1, Join the node in the team .
If the number of floors of the outgoing node is the target floor b, Then the number of keystrokes of this node is from a To b Minimum number of keystrokes .

【 Solution code 】

solution 1： Guang Shu

#include<bits/stdc++.h>
using namespace std;
#define N 205
struct Node
{
    
	int x, s;//x: Floor number  s: Number of buttons  
	Node(){
    }
	Node(int a, int b):x(a), s(b){
    }
};
int n, a, b, np, k[N];
bool vis[N];//vis[i]: The first i The position has passed  
int bfs()
{
    
    queue<Node> que;
	vis[a] = true;
	que.push(Node(a, 0));// The initial state ： In the a layer , Press 0 Time  
	while(que.empty() == false)
	{
    
		Node u = que.front();
		que.pop();
		if(u.x == b)
			return u.s;
		int x[2] = {
    u.x + k[u.x], u.x - k[u.x]};// Two possible next arrival floors  
		for(int i = 0; i < 2; ++i)
		{
    
    		if(x[i] >= 1 && x[i] <= n && vis[x[i]] == false) 
    		{
    
    			vis[x[i]] = true;
    			que.push(Node(x[i], u.s + 1));
    		}
    	}
	}
	return -1;// If it doesn't arrive b layer  
}
int main()
{
    
	cin >> n >> a >> b;
	for(int i = 1; i <= n; ++i)
		cin >> k[i];
	cout << bfs();
	return 0;
}