Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"cycleck","updateTime":1531571080000,"title":"Tunnels ","dislikeCnt":2,"content":"状态压缩+裸广搜\n二进制记录某个隧道是否已经过,广搜预处理每个出口与其他所有入口的距离\n```\n#include\u003ccstdio\u003e\n#include\u003ccstring\u003e\n#include\u003cqueue\u003e\n#include\u003calgorithm\u003e\n#include\u003ciostream\u003e\n#define inf 0x3f3f3f3f\nusing namespace std;\nconst int f[4][2]\u003d{{1,0},{-1,0},{0,1},{0,-1}};\nint n,m,dis[20][20],enx,eny,dp[33000][20];//enx和eny记录入口坐标,dp记录在j-th个隧道时的状态为i的所走长度\nstruct zb{ //记录每条隧道的出入口坐标\n int x1,y1,x2,y2;\n}z[20];\nstruct point_dis{\n int x,y,d;\n};\nbool vis[20][20],map[20][20];//vis标记已走点,map标记不可走的点\nint bfs(int x0,int y0){\n memset(vis,false,sizeof(vis));//记得清空标记\n queue\u003cpoint_dis\u003e q;//申请一个队列\n point_dis start,end;\n start.x\u003dx0,start.y\u003dy0,start.d\u003d0;\n q.push(start);\n vis[x0][y0]\u003dtrue;\n while(q.size()){\n start\u003dq.front();\n q.pop();\n if(start.x\u003d\u003denx\u0026\u0026start.y\u003d\u003deny) return start.d;//最早结束的结果一定是最短距离\n for(int i\u003d0;i\u003c4;i++){\n int x_now\u003dstart.x+f[i][0];\n int y_now\u003dstart.y+f[i][1];\n if(x_now\u003c1||x_now\u003en||y_now\u003c1||y_now\u003en||vis[x_now][y_now]||!map[x_now][y_now])continue;\n vis[x_now][y_now]\u003dtrue;\n end.x\u003dx_now,end.y\u003dy_now;\n end.d\u003dstart.d+1;\n q.push(end);\n }\n }\n return inf;\n}\nint main(){\n while(scanf(\"%d%d\",\u0026n,\u0026m)!\u003dEOF){\n for(int i\u003d1;i\u003c\u003dn;i++){\n for(int j\u003d1;j\u003c\u003dn;j++){\n char c;\n cin\u003e\u003ec;\n if(c\u003d\u003d\u0027#\u0027)map[i][j]\u003dfalse;\n else map[i][j]\u003dtrue;\n }\n }\n for(int i\u003d0;i\u003cm;i++)\n scanf(\"%d%d%d%d\",\u0026z[i].x1,\u0026z[i].y1,\u0026z[i].x2,\u0026z[i].y2);\n memset(dis,inf,sizeof(dis));\n for(int i\u003d0;i\u003cm;i++){\n for(int j\u003d0;j\u003cm;j++){\n if(i\u003d\u003dj) continue;\n enx\u003dz[j].x1,eny\u003dz[j].y1;\n int d\u003dbfs(z[i].x2,z[i].y2);\n dis[i][j]\u003dd;\n }\n }\n int a\u003d1\u003c\u003cm;\n for(int i\u003d0;i\u003ca;i++)\n for(int j\u003d0;j\u003cm;j++)\n dp[i][j]\u003dinf;\n for(int i\u003d0;i\u003cm;i++)dp[(1\u003c\u003ci)][i]\u003d0;//初始化\n int ans\u003dinf;\n for(int i\u003d1;i\u003ca;i++){//枚举状态\n int flag\u003d1;\n for(int j\u003d0;j\u003cm;j++){//枚举起点(一步)\n if(!(i\u0026(1\u003c\u003cj))){\n flag\u003d0;\n continue;\n }\n for(int k\u003d0;k\u003cm;k++){//枚举终点(一步)\n if(!(i\u0026(1\u003c\u003ck))||j\u003d\u003dk)continue;\n dp[i][j]\u003dmin(dp[i][j],dp[i^(1\u003c\u003cj)][k]+dis[k][j]);\n }\n }\n if(flag)\n for(int j\u003d0;j\u003cm;j++)\n ans\u003dmin(ans,dp[i][j]);\n }\n if(ans\u003d\u003dinf) cout\u003c\u003c-1\u003c\u003cendl;\n else cout\u003c\u003cans\u003c\u003cendl;\n }\n return 0;\n}\n\n```\n\n~~关爱蒟蒻QwQ~~\nTIPS:\n queue(队列) 模板类的定义在\u003cqueue\u003e头文件中queue 模板类需要两个模板参数,一个是元素类型,一个容器类型,\n 元素类型是必要的,容器类型是可选的,默认为deque 类型定义queue 对象的示例代码如下:\n queue\u003cint\u003e q1;\n queue\u003cdouble\u003e q2;\nqueue 的基本操作有:\n 入队,如例:q.push(x); 将x 接到队列的末端。\n 出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。\n 访问队首元素,如例:q.front(),即最早被压入队列的元素。\n 访问队尾元素,如例:q.back(),即最后被压入队列的元素。\n 判断队列空,如例:q.empty(),当队列空时,返回true。\n 访问队列中的元素个数,如例:q.size()\n\n优先队列\n一个优先队列声明的基本格式是:\npriority_queue\u003c结构类型\u003e 队列名;\n比如:\n priority_queue \u003cint\u003e i;\n priority_queue \u003cdouble\u003e d;\n常用的是这几种:\npriority_queue \u003cnode\u003e q;node是一个结构体,其中重载了‘\u003c’小于符号\npriority_queue \u003cint,vector\u003cint\u003e,greater\u003cint\u003e \u003e q;不需要#include\u003cvector\u003e头文件\n注意后面两个“\u003e”不要写在一起,“\u003e\u003e”是右移运算符\npriority_queue \u003cint,vector\u003cint\u003e,less\u003cint\u003e \u003eq;\n优先队列的特性: 自动排序\n默认的优先队列(非结构体结构)priority_queue \u003cint\u003e q;是从大到小摆列的 。\n而对于结构体结构\nstruct node{\n int x,y;\n bool operator \u003c (const node \u0026 a) const{\n return x\u003ca.x;\n }\n};这个node结构体有两个成员,x和y,它的小于规则是x小者小。\nless和greater优先队列\n还是以int为例,先来声明\npriority_queue \u003cint,vector\u003cint\u003e,less\u003cint\u003e \u003e p;\npriority_queue \u003cint,vector\u003cint\u003e,greater\u003cint\u003e \u003e q;\nless是从大到小,greater是从小到大。 \n在平时,建议写\npriority_queue\u003cint,vector\u003cint\u003e,less\u003cint\u003e \u003eq;\npriority_queue\u003cint,vector\u003cint\u003e,greater\u003cint\u003e \u003eq;\n平时如果用从大到小不用后面的vector\u003cint\u003e,less\u003cint\u003e,可能到时候要改成从小到大,你反而会搞忘怎么写greater\u003cint\u003e,反而得不偿失。","threadId":31515,"likeCnt":0,"createTime":1531571080000,"isWorkbook":false,"viewCnt":1665,"openness":2,"fav":false,"id":521,"trustable":false}