题目：P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态

类型：搜索

dfs做法

1用例会TLE

注意要点

1.往上走 往下走 去深搜（判断是否能走）

2.是否已经访问这个节点（如果访问，则没有意义）剪枝1

3.当step<=ans 才有继续搜索的必要 剪枝2

代码：

#include <bits/stdc++.h>

using namespace std;


const int N = 205;
const int INF = 0x3f3f3f3f;
int n, a, b, minn;
int k[N];
int is_vis[N];	//有没有去过


void search(int x, int step)
{
	if (x == b)
	{
		minn = min(minn, step);
		return;
	}
	else if (step <= minn)			//只有比 minn小的  才有必要继续搜下去
	{
		is_vis[x] = 1;			//来过
		//往上走
		//能往上  并且没有来过  如果来过  很有可能就死循环了
		if (x + k[x] <= n  && !is_vis[x + k[x]])
		{
			search(x + k[x], step + 1);
		}

		//往下走
		if (x - k[x] >= 1 && !is_vis[x - k[x]])
		{
			search(x - k[x], step + 1);
		}
		is_vis[x] = 0;			//回溯
	}



}


int main ()
{
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++)
	{
		cin >> k[i];
	}
	minn = INF, is_vis[a] = 1;
	search(a, 0);
	if (minn != INF)
		cout << minn;
	else
		cout << "-1";



}

然后就

bfs做法

注意要点

入队列的时候就需要把节点 设置为访问

而不是在出的时候 不然会产生死循环

例如 3入队列了 但是刚刚出去的 是能到达3的 但是3还没有出 没有被标记上已经访问 就又回走回3

代码

#include <bits/stdc++.h>


using namespace std;

const int N = 205;
const int INF = 0x3f3f3f3f;
int a, b, n, ans = INF;
int k[N], is_vis[N];

typedef pair<int, int > PII;		//first 当前所处楼层    second  到此楼层所用步数
queue<PII> q;
PII tmp;

void bfs(PII x)
{
	q.push(x);

	while (!q.empty())
	{
		tmp = q.front();
		q.pop();

		if (tmp.first == b)
		{
			ans = tmp.second;
			break;
		}
		//往上走
		//能走 且没有被访问过

		if (tmp.first + k[tmp.first] <= n && ! is_vis[tmp.first + k[tmp.first]])
		{
			//入队
			q.push(make_pair(tmp.first + k[tmp.first], tmp.second + 1));
			is_vis[tmp.first + k[tmp.first]] = 1;
		}


		//往下走
		//能走 且没有被访问过

		if (tmp.first - k[tmp.first] <= n && ! is_vis[tmp.first - k[tmp.first]])
		{
			//入队
			q.push(make_pair(tmp.first - k[tmp.first], tmp.second + 1));
			is_vis[tmp.first - k[tmp.first]] = 1;
		}
	}


}


int main ()
{
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++)
	{
		cin >> k[i];
	}
	is_vis[a] = 1;
	bfs(make_pair(a, 0));
	if (ans != INF)
		cout << ans;
	else
		cout << "-1";

}