电商扶贫网站建设,自己创做网站,怎么开微信公众号,wordpress菜单二级菜单题目链接#xff1a;Planning mobile robot on Tree (EASY Version) 题目描述#xff1a; 给定一棵树#xff0c;树上有一个位置存在一个机器人#xff0c;其他mmm个位置存在石头#xff0c;保证初始状态一个结点最多一个物体#xff08;一个石头或者一个机器人或者为空…题目链接Planning mobile robot on Tree (EASY Version) 题目描述 给定一棵树树上有一个位置存在一个机器人其他mmm个位置存在石头保证初始状态一个结点最多一个物体一个石头或者一个机器人或者为空你的任务是用尽量少的操作将机器人移动到目标结点如果不能到达输出−1-1−1如果可以输出路径如果存在多条最小路径输出任意一条即可。你可以执行的操作如下 将一个机器人移动到与其相邻的某个空结点上。将一个石头移动到与其相邻的某个空结点上。 题解 本题可以使用BFSBFSBFS来做由于最多有151515个结点我们可以用一个151515位的二进制来表示某个结点是否存在石头或者机器人同时我们可以用一个变量来记录某个状态的机器人的位置。那么我们只需要进行简单的BFSBFSBFS即可找到最短路径 dis[s][i]dis[s][i]dis[s][i]表示当前状态为sss机器人的位置在jjj时需要的移动次数。那么移动的操作(u,v)(u,v)(u,v)可行的条件是 sss中uuu位置有东西u,vu,vu,v之间存在边sss中vvv位置没有东西一个不能存在两个物体 如何进行路径点的输出路径的输出有很多种方法我采用的是记录每个状态的上一次的状态然后通过递归来输出状态这里也可以使用一个栈来输出只要满足先进后出即可当前的状态与转移到当前状态的标记不同的结点就是发生了移动操作的结点。 代码
#include bits/stdc.hconst int MAXN 15;
const int MAXM MAXN - 2;using namespace std;int dis[1 16][MAXN];
int haveStone[MAXN], head[MAXN];
int T, n, m, s, t, stonePos, caseID, ecnt, u, v;typedef pairint, int State;State ans;
State pre[1 16][MAXN];struct EdgeList
{int to;int nex;
}es[MAXN 1];void addEdge(int u, int v)
{es[ecnt].to v;es[ecnt].nex head[u];head[u] ecnt;
}State getInitialState()
{int status 0;for (int i 0; i n; i) { status | (int)haveStone[i] i; }status | 1 s;return make_pair(status, s);
}void bfs()
{queueState q;State initialState getInitialState();dis[initialState.first][initialState.second] 0;q.push(initialState);State now, newState;while (!q.empty()) {now q.front();q.pop();if (now.second t) {ans now;return;}for (int u 0; u n; u) {if (((1 u) now.first) 0) { continue; }for (int i head[u]; i ! -1; i es[i].nex) {int v es[i].to; // 进行u-v的移动if (((1 v) now.first) ! 0) { continue; }newState.first now.first ^ (1 u) ^ (1 v);if (u now.second) { newState.second v; }else { newState.second now.second; }if (dis[newState.first][newState.second] ! -1) { continue; }dis[newState.first][newState.second] dis[now.first][now.second] 1;pre[newState.first][newState.second] now;q.push(newState);}}}
}void print(State now)
{if (now.second -1 || pre[now.first][now.second].second -1) { return; }print(pre[now.first][now.second]);for (int i 0; i n; i) {if ((now.first (1 i)) 0 (pre[now.first][now.second].first (1 i)) ! 0) {u i 1;}if ((now.first (1 i)) ! 0 (pre[now.first][now.second].first (1 i)) 0) {v i 1;}}cout u v endl;
}void printPath()
{caseID;cout Case caseID : ;if (ans.second -1) {cout -1 endl;return;}cout dis[ans.first][ans.second] endl;print(ans);cout endl;
}void init()
{ecnt 0;ans.second -1;memset(pre, -1, sizeof(pre));memset(dis, -1, sizeof(dis));memset(head, -1, sizeof(head));memset(haveStone, 0, sizeof(haveStone));
}int main()
{cin T;while (T--) {init();cin n m s t; s--; t--;for (int i 0; i m; i) {cin stonePos; stonePos--;haveStone[stonePos] true;}for (int i 0; i n - 1; i) {cin u v; u--; v--;addEdge(u, v); addEdge(v, u);}bfs();printPath();}return 0;
}
