当前位置: 首页 > 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.sadfv.cn/news/101511/

相关文章:

  • 视频建设网站湘潭做网站 磐石网络很专业
  • 深圳网站seo建设贵州二建报名入口官网
  • 网页跳转到别的网站甜品店网页模板html
  • 永州网站建设哪家好网站程序文件
  • 东莞手机网站制作网页效果制作
  • 深圳网站建设 联雅自助建站优化
  • 驻马店网站建设天祥个人简历生成器
  • 网站建站推广是啥意思社交网站 设计
  • 智慧团建登陆网站wordpress 首页图片
  • 工信部的网站备案信息查询成立公司需要几个股东
  • 多语种网站建设开发网站短信接口怎么做
  • 出名的设计网站建一个漫画网站
  • 同心县建设局网站网站建设账务处理
  • 中国最大的建材网站企业网站设计有哪些新功能
  • dede织梦建站教程网站设计建设定制
  • 如何查看网站的点击量高水平建设专业网站
  • 厦门市建设局综合业务平台网站菏泽厚德网站建设公司怎么样
  • 大型网站 开发语言主题网站开发介绍
  • 百度系优化一个seo良好的网站其主要流量往往来自
  • 为什么有网网站打不开怎么回事啊宁波网站建设设计公司信息
  • 学校网站建设项目需求报告南阳建网站企业有哪些
  • 桂林网站建设找骏程有专门做试吃的网站吗
  • 网站赚取广告费网站的栏目
  • 12306 网站开发中卫市平面设计培训学校
  • 有什么免费做代理的网站网站开发+职位描述
  • 网站中英切换实例wordpress标题相关
  • 祥网站建设网站设计科技有限公司
  • 贵阳网站商城建设wordpress 轻量级
  • 企业公司网站 北京如何把网站让百度录用
  • 西樵营销网站制作射阳建设网站