当前位置: 首页 > news >正文

昆明建设路租房信息昆明租房网站柘城网站建设

昆明建设路租房信息昆明租房网站,柘城网站建设,建立网站地图,aspnet网站开发 视频题目传送门 题意#xff1a;给出一个$N \times M$的棋盘#xff0c;棋盘上有一些块可以移动#xff0c;有一些块无法移动。$Q$次询问#xff0c;每一次询问给出三个块$a,b,c$#xff0c;将$a$块变为空格#xff0c;空格旁边可移动的块可以与空格交换位置。问每一次询问中…题目传送门 题意给出一个$N \times M$的棋盘棋盘上有一些块可以移动有一些块无法移动。$Q$次询问每一次询问给出三个块$a,b,c$将$a$块变为空格空格旁边可移动的块可以与空格交换位置。问每一次询问中最小的将$b$块移动到$c$块最开始位置上的移动次数。$N , M \leq 30 , Q \leq 500$ 我觉得我在$NOIP$考场上绝对会直接打暴力qwq 我们能够发现空格必须要在需要移动的格子的四周而且不移动需要移动的格子才能发挥效果。所以当空格在需要移动的格子旁边的时候只有两种情况①将需要移动的格子与空格交换位置②将空格移动到需要移动的格子的另一侧。所以我们预处理$f_{i,j,k,l}$表示将空格从格子$i,j$的方向$k$移动到方向$l$且不移动$(i,j)$的最少步数可以通过$bfs$实现复杂度$O(16N^2M^2)$ 接下来就是一个类似于最短路的问题了。然而最开始空格与需要移动的格子不相邻所以我们在每一次询问的时候再一次$bfs$计算现在空格的位置到达需要移动的格子四周且不移动需要移动的格子的最少移动次数然后跑$SPFA$即可。因为图很小卡不了$SPFA$。 1 #includebits/stdc.h2 using namespace std;3 4 inline int read(){5 int a 0;6 char c getchar();7 while(!isdigit(c))8 c getchar();9 while(isdigit(c)){10 a (a 3) (a 1) (c ^ 0);11 c getchar();12 }13 return a;14 }15 16 const int dir[4][2] {0,1,1,0,-1,0,0,-1};17 int f[31][31][4][4] , dis[31][31][4] , t[31][31] , N , M , Q;18 bool canbe[32][32] , inq[31][31][4];19 struct be{20 int x , y , dir;21 }now;22 23 queue pair int , int q;24 queue be q1;25 26 inline int SPFA(int aX , int aY , int bX , int bY , int cX , int cY){27 while(!q.empty())28 q.pop();29 if(!canbe[aX][aY] || !canbe[bX][bY])30 return 0x3f3f3f3f;31 memset(t , 0x3f , sizeof(t));32 t[aX][aY] 0;33 q.push(make_pair(aX , aY));34 while(!q.empty()){35 pair int , int r q.front();36 q.pop();37 if(r.first bX r.second bY)38 return t[bX][bY];39 for(int i 0 ; i 4 ; i)40 if(r.first dir[i][0] ! cX || r.second dir[i][1] ! cY)41 if(canbe[r.first dir[i][0]][r.second dir[i][1]])42 if(t[r.first dir[i][0]][r.second dir[i][1]] t[r.first][r.second] 1){43 t[r.first dir[i][0]][r.second dir[i][1]] t[r.first][r.second] 1;44 q.push(make_pair(r.first dir[i][0] , r.second dir[i][1]));45 }46 }47 return 0x3f3f3f3f;48 }49 50 inline void bfs(int sX , int sY , int tX , int tY){51 for(int i 0 ; i 4 ; i)52 if(dis[sX][sY][i] ! 0x3f3f3f3f){53 inq[sX][sY][i] 1;54 q1.push((be){sX , sY , i});55 }56 while(!q1.empty()){57 now q1.front();58 inq[now.x][now.y][now.dir] 0;59 q1.pop();60 if(now.x tX now.y tY)61 continue;62 for(int i 0 ; i 4 ; i)63 if(now.dir ! i){64 int N dis[now.x][now.y][now.dir] f[now.x][now.y][now.dir][i];65 if(dis[now.x][now.y][i] N){66 dis[now.x][now.y][i] N;67 if(!inq[now.x][now.y][i]){68 inq[now.x][now.y][i] 1;69 q1.push((be){now.x , now.y , i});70 }71 }72 }73 if(dis[now.x dir[now.dir][0]][now.y dir[now.dir][1]][3 - now.dir] dis[now.x][now.y][now.dir] 1){74 dis[now.x dir[now.dir][0]][now.y dir[now.dir][1]][3 - now.dir] dis[now.x][now.y][now.dir] 1;75 if(!inq[now.x dir[now.dir][0]][now.y dir[now.dir][1]][3 - now.dir]){76 inq[now.x dir[now.dir][0]][now.y dir[now.dir][1]][3 - now.dir] 1;77 q1.push((be){now.x dir[now.dir][0] , now.y dir[now.dir][1] , 3 - now.dir});78 }79 }80 }81 }82 83 int main(){84 N read();85 M read();86 Q read();87 for(int i 1 ; i N ; i)88 for(int j 1 ; j M ; j)89 canbe[i][j] read();90 memset(f , 0x3f , sizeof(f));91 for(int i 1 ; i N ; i)92 for(int j 1 ; j M ; j)93 if(canbe[i][j])94 for(int m 0 ; m 3 ; m)95 for(int n 0 ; n 3 ; n)96 f[i][j][m][n] SPFA(i dir[m][0] , j dir[m][1] , i dir[n][0] , j dir[n][1] , i , j);97 while(Q--){98 int a read() , b read() , c read() , d read() , e read() , f read();99 if(c e d f){ 100 printf(0\n); 101 continue; 102 } 103 memset(dis , 0x3f , sizeof(dis)); 104 for(int i 0 ; i 4 ; i) 105 dis[c][d][i] SPFA(a , b , c dir[i][0] , d dir[i][1] , c , d); 106 bfs(c , d , e , f); 107 int ans 0x3f3f3f3f; 108 for(int i 0 ; i 4 ; i) 109 ans min(ans , dis[e][f][i]); 110 printf(%d\n , ans 0x3f3f3f3f ? -1 : ans); 111 } 112 return 0; 113 }  转载于:https://www.cnblogs.com/Itst/p/9782108.html
http://www.huolong8.cn/news/101511/

相关文章:

  • 校园二手书交易网站开发网站条形码如何做
  • 站长工具查询wordpress 调用豆瓣
  • 农业大学网站建设特点江苏省建设招标网站
  • 成都百度网站设计公司免费写作文网站
  • 成都网站建设空间拓者设计吧室内设计官网免费账号
  • 岳溥庥网站建设网站交互做的比较好的
  • seo 网站优化世界500强企业关于优秀员工的12条核心标准
  • 可不可以自己做网站做一个网站做少多少钱
  • 企业网站开发 文献综述网站建设成本计划
  • 支付的网站建设费整么做账上传wordpress后网页为什么空白
  • php .net做网站哪个好厦门网站建设小程序开发
  • 企业做网站的费用如果做账wordpress 前台插件
  • 别人 网站 粘贴 html 推广微信营销的方法和技巧
  • asp网站免费完整源码手机qq空间登录网页入口
  • 山西省建设监理协会官方网站济南便宜企业网站建设费用
  • 网站开发团队公司模式wordpress wordpress
  • 网站3级营销是怎么做的这个网站中有网名做会计的吗 了解一下
  • 花都高端网站建设系统开发的步骤
  • 个人网站建设收费标准广东省建设厅人才网站
  • 复古风格网站网站建设合同 售后维护期
  • 做外贸什么网站好广州网站建设骏域网站建设专家
  • 承德网站建设设计代做电大网站ui作业
  • 用asp做网站需要安装什么软件东莞代理公司注册
  • 杭州 建设网站制作静态网站提交表单怎么做
  • 赣州章贡区邮编长沙seo优化外包公司
  • 网站有必要使用伪静态么四川网站建设有哪些
  • 建设一个类似于猪八戒的网站需要云商城官网
  • 网站制作模板免费下载wordpress it博客主题
  • 萧县做网站南平网站建设公司
  • dede网站怎么更换模板做网站每天都要花钱么