題意：有一顆n個(gè)節(jié)點(diǎn)的樹(shù)，其中一個(gè)節(jié)點(diǎn)有機(jī)器人，指定m個(gè)節(jié)點(diǎn)有障礙物，指定終點(diǎn)，問(wèn)最少需要移動(dòng)多少步才能到達(dá)，移動(dòng)過(guò)程中遇到障礙物需要將其移動(dòng)到空地。

分析：bfs搜索，是每次都對(duì)障礙物進(jìn)行移動(dòng)，將障礙物移動(dòng)到空閑地方，如果是機(jī)器人移動(dòng)就需要更新位置。

障礙物位置用二進(jìn)制儲(chǔ)存，方便查找，更新。

# include<iostream> # include<cstdio> # include<cmath> # include<map> # include<queue> # include<string> # include<string.h> #include<set> #include<list> # include<algorithm> using namespace std; const int maxn = 1 << 20; struct node {int state, pos, pre, len;node(){}node(int _state,int _pos,int _pre,int _len):state(_state),pos(_pos),pre(_pre),len(_len){} }; vector<int>G[20]; node q[maxn]; int vis[20][maxn]; int n, obnum, s, t; int start,step; void bfs(int ob) {int front = 0, rear = 1;node temp(ob, s, -1, 0);q[front] = temp;vis[s][ob] = 1;while (front < rear) {node u = q[front];if (u.pos == t) {//移動(dòng)到終點(diǎn)就退出start = front;step = u.len;break;}for (int i = 0; i < n; i++) {if ((1 << i)&u.state) {//找到障礙物位置for (int j = 0; j < G[i].size(); j++) {int next = G[i][j];if ((1 << next)&u.state)continue;//找到空閑位置node ttd = u;ttd.pos = u.pos; ttd.state = ((u.state|(1<<next))^(1<<i));if (ttd.pos == i)ttd.pos = next;//如果是機(jī)器人移動(dòng)，就更新位置if (!vis[ttd.pos][ttd.state]) {vis[ttd.pos][ttd.state] = 1;ttd.len++;ttd.pre = front;q[rear++] = ttd;}}}}front++;} } void result(int u) {if (q[u].pre != 0)result(q[u].pre);//從前往后輸出int last = q[q[u].pre].state;int cur = q[u].state;;int a, b;a = last ^ (last&cur);//因?yàn)槊看沃灰苿?dòng)一步b = cur ^ (last&cur);int aa, bb;for (int i = 0; i < n; i++) {if ((1 << i)&a)aa = i;if ((1 << i)&b)bb = i;}cout << aa + 1 << " " << bb + 1 << endl; } int main() {int kase;cin >> kase;for (int k = 0; k < kase; k++) {for (int i = 0; i < 20; i++)G[i].clear();memset(vis, 0, sizeof(vis));step = -1;cin >> n >> obnum >> s >> t;int obstacle = 0;s--, t--;for (int i = 0; i < obnum; i++) { int l;cin >> l;l--;obstacle |= (1<<l);}for (int i = 0; i < n - 1; i++) { int temp,temp1; cin >> temp>>temp1;G[temp-1].push_back(temp1-1);G[temp1-1].push_back(temp-1);}obstacle |= (1 << s);bfs(obstacle);cout << "Case " << k + 1 << ": ";if (step == -1) {cout << "-1" << endl;}else {cout << step << endl;result(start);}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的UVA - 12569 Planning mobile robot on Tree (EASY Version) BFS的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。