深圳整站全网推广微信公众号登录官方入口

深圳整站全网推广,微信公众号登录官方入口,wordpress有哪些网站,公司和公司网站的关系【题目链接】 ybt 1453#xff1a;移动玩具 洛谷 P4289 [HAOI2008] 移动玩具 【题目考点】 1. 广搜 2. 双向广搜 3. map map存储键值对 由于map底层是红黑树#xff08;一种二叉搜索树#xff09;#xff0c;其键的类型必须可以比较#xff0c;即键的类型支持…【题目链接】ybt 1453移动玩具洛谷 P4289 [HAOI2008] 移动玩具【题目考点】1. 广搜2. 双向广搜3. mapmap存储键值对由于map底层是红黑树一种二叉搜索树其键的类型必须可以比较即键的类型支持小于号运算符。【解题思路】解法1广搜本题以4*4二维数组作为状态状态中包含了移动玩具的步数。输入起始和目标状态。设队列保存状态将起始状态入队。每次循环出队一个状态u uu为当前状态。从当前状态u uu出发遍历二维数组中的每个位置。如果当前位置是1那么尝试将1向其上下左右四个方向移动其目标移动位置必须在二维数组范围内且目标位置为0。如果可以移动那么将当前位置和目标位置的值交换完成移动得到新的状态t tt。对于新的状态t tt先使用vis判断该状态是否出现过。如果该状态没有出现过则记录到达该状态经过的步数dis将t tt状态入队。而后进行下一次循环。当出队的状态为目标状态时返回到达目标状态的步数即为本题的结果。广搜过程中需要判断某一状态是否已经出现过。本题的状态为一个4*4二维数组因此需要记录一个4*4二维数组是否出现过。设Node类型保存状态其中包含一个char类型的二维数组。需要使用一组映射记录状态是否出现过。方法1键类型Node值类型bool由于map的键的类型必须可以比较即实现小于号运算符。我们需要对Node类型重载小于号运算符使得两个Node类型对象可以使用小于号运算符进行比较。其声明格式为booloperator(constNodeb)const{//...}注意函数中的两个const必须写这是map类的要求。此处可以自己定义一种比较规则即给定两个二维数组你可以根据该规则说出哪个更大哪个更小即可。以下给出一个可行的比较规则。可以按顺序依次比较两个状态的二维数组的每个对应位置的值。如果第一个数组中取到的值小于第二个数组中取到的值返回真。如果第一个数组中取到的值大于于第二个数组中取到的值返回假。如果第一个数组和第二个数组完全相同也返回假。方法2键类型string值类型boolstring类已经重载了小于号运算符可以根据字典序规则比较两个字符串。在Node类型中将二维数组转为string。只需要遍历二维数组将取到的字符连接为一个字符串即可。解法2双向广搜可以从起始状态和目标状态同时出发进行广搜首先将起始和目标状态同时入队。vis为一个map记录一个状态来源即该状态是从哪个状态扩展得到的值为0表示该状态还没出现过。值为1表示该状态是从起始状态扩展得到的。值为2表示该状态是从最终状态扩展得到的。该方法必须设一个独立的名为dis的map来记录到达一个状态的步数无法把dis放在Node类中。搜索过程和广搜类似从当前状态u uu扩展得到一个新的状态t tt时如果t tt状态未出现过那么将t tt状态的来源vis[t]设为和当前u uu状态的来源vis[u]相同。如果t tt状态已出现过且t tt状态的来源vis[t]和当前u uu状态的来源vis[u]不同说明在解空间树上从起始状态出发的路径和从目标状态出发的路径相遇。从一个来源到u uu状态的步数为dis[u]从另一个来源到t tt状态的步数为dis[t]从起始状态到目标状态的总步数为dis[u]dis[t]1。将该值返回即为问题的结果。记录状态的方法可以使用上述方法1在Node中重载小于号运算符而后将Node作为map的键。或使用方法2将状态转为string而后作为map的键。【题解代码】解法1广搜Node中重载小于号运算符#includebits/stdc.husingnamespacestd;structNode{chara[5][5];intdis;//到达该状态的步数booloperator(constNodeb)const{for(inti1;i4;i)for(intj1;j4;j)if(a[i][j]!b.a[i][j])returna[i][j]b.a[i][j];returnfalse;}booloperator(constNodeb)const{for(inti1;i4;i)for(intj1;j4;j)if(a[i][j]!b.a[i][j])returnfalse;returntrue;//两数组相同}};Node st,ed;mapNode,boolvis;intdir[4][2]{{0,1},{0,-1},{1,0},{-1,0}};intbfs(){queueNodeque;que.push(st);vis[st]true;while(!que.empty()){Node uque.front(),tu;//t临时变量que.pop();if(ued)//使用returnu.dis;for(inti1;i4;i)for(intj1;j4;j)if(u.a[i][j]1)//(i,j)位置是玩具for(intk0;k4;k){intxidir[k][0],yjdir[k][1];//(x,y)移动的目标位置if(x1x4y1y4u.a[x][y]0){swap(t.a[i][j],t.a[x][y]);if(!vis[t]){vis[t]true;t.disu.dis1;que.push(t);}swap(t.a[i][j],t.a[x][y]);//将t还原为和u相同}}}return-1;//如果无解返回-1尽管题目没有要求}intmain(){for(inti1;i4;i)for(intj1;j4;j)cinst.a[i][j];for(inti1;i4;i)for(intj1;j4;j)cined.a[i][j];coutbfs();return0;}解法2双向广搜使用string表示状态#includebits/stdc.husingnamespacestd;structNode{chara[5][5];stringstr(){string s;for(inti1;i4;i)for(intj1;j4;j)s.push_back(a[i][j]);returns;}};Node st,ed;mapstring,intvis,dis;intdir[4][2]{{0,1},{0,-1},{1,0},{-1,0}};intbfs(){queueNodeque;que.push(st);que.push(ed);vis[st.str()]1,vis[ed.str()]2;if(vis.size()1)return0;//起点终点相同while(!que.empty()){Node uque.front(),tu;//t临时变量que.pop();for(inti1;i4;i)for(intj1;j4;j)if(u.a[i][j]1)//(i,j)位置是玩具for(intk0;k4;k){intxidir[k][0],yjdir[k][1];//(x,y)移动的目标位置if(x1x4y1y4u.a[x][y]0){swap(t.a[i][j],t.a[x][y]);if(vis[t.str()]0){vis[t.str()]vis[u.str()];dis[t.str()]dis[u.str()]1;que.push(t);}elseif(vis[t.str()]!vis[u.str()])//相遇returndis[t.str()]dis[u.str()]1;swap(t.a[i][j],t.a[x][y]);}}}}intmain(){for(inti1;i4;i)for(intj1;j4;j)cinst.a[i][j];for(inti1;i4;i)for(intj1;j4;j)cined.a[i][j];coutbfs();return0;}