题目链接洛谷链接https://www.luogu.com.cn/problem/P4011AcWing链接https://www.acwing.com/problem/content/1133/涉及知识1.单源最短路2.双端队列广度优先搜索3.状态压缩动态规划和二进制的巧用思路分析第一部分题意的抽象——建图首先我们看到这一题不难想到这是一个限制条件较多的最短路那么我们就很自然地需要探索如何将本题的门、墙、钥匙等抽象成图、边等元素。图的基本元素是点和边因此我们也就围绕着两个元素展开。点点即当前麦克所在的地方。本题是以坐标的形式给到我们的这方便我们进行DFS或者BFS的转移但是不方便我们运用最短路算法的我们可以通过初始化赋值将每一个二维坐标转化为一维坐标并且在题中灵活运用这两种坐标。这一点会在之后的代码中有所体现同时每个点可能会有钥匙也就是说与经典最短路相比我们还需要考虑走到当前点时我们手中拿到的钥匙的情况。对于这一点我们可以借鉴状态压缩动态规划的思想将当前拿到的钥匙的情况用二进制数表示。特别注意本题中同一处地方可能会有多把钥匙因此我们在读入钥匙的坐标时不能简单地用等于而是用或操作合并。在宽搜走到要通过大门时则读取状态判断有无该类型的钥匙。在这里对于所涉及的二进制操作在状态压缩中的利用进行简单介绍至于每一种运算符的含义如果没有接触过请自行查阅资料有学过状压的可以略过1.简介在信息学的题目中我们常用二进制数来表示某一种状态比如动态规划中当前我们持有的物品。以本题为例我们想用二进制数表示当前我们持有x xx类型的钥匙本质上就是让二进制数的第x xx位变成 1 。在之后的读取中哪一位有 1就说明我们有哪一种钥匙。这也就解释了为什么开数组时的P PP要设置为1 10 110110(即等同于2 10 2^{10}210)因为共有 10 钟类型的钥匙每一种类型的钥匙我么可能持有状态为1可能没有状态为0两种情况。2.合并状态在二进制操作中我们采用或操作来合并两种状态。这里可以类比数学中的集合一个集合我们做并集运算其实就是把两个集合都有的元素通通放进来。或操作对两个二进制数的每一位进行判断只要其中有 1 位为 1结果便为 1也就是说只要我两种状态中有任意一种状态拥有这种类型的钥匙最后结果都会拥有。通过或操作我们就保证了当一个地方有多种类型的钥匙时结果都在取并集。3.读入状态以此题为例当我们拥有x xx类型的钥匙时读入便是让二进制数的第x xx位为 1。通过左移x xx位让第x xx位变成1得到一个新二进制数000..1...00 000..1...00000..1...001在第x xx位再用当前状态的二进制数和它做或运算即可得到新状态。4.读取状态读取状态便是希望取出第x xx位的数字判断其是否为1 11从而得出是否拥有x xx类型的钥匙。设当前状态为s ss则通过右移操作s x sxsx是在取出第x xx位s x 1 sx\1sx1就是在判断第x xx位是否为 1。边边即题中的门、墙和其他自由通行的路径。1.门和墙门我们可以直接读入将边权设定为其所属的类型即可。需要注意的是墙我们是不需要读入的因为我们是在做图论题只要不建边就不会有这条路也就不会通行了。2.自由通行的路径自由通行的路径相当于一扇不需要任何钥匙的“门”所以可以在读入完门和墙的数据之后用一个函数把自由通行的路径一次性初始化好设定为边权为 0 的边。为了防止给一扇门或者一堵墙所在的那条边也建上自由通行的路径我们可以在读入门和墙的时候用s e t setset统计已经出现的边。第二部分最短路的实现在本题中我们可以将捡到钥匙看作边权为 0 的边将朝四周走看作边权为 1 的边也就是两种可能的情况然后运用双端队列BFS即可得出走到瑞恩处的最短距离。需要注意的是此处的边权并非上面我们建边时的边权建边时我们只是用存储边权的数组存储了钥匙的类型而我们真正意义上的边权即我们跑最短路时走一步加的那个数字只是1。第三部分思路再梳理第一步读入n , m , p , k n,m,p,kn,m,p,k以及门和墙的数据统计所有已经出现的门和墙类型为门的边进行建边然后将其他可以自由通行的路径统一建边第二步读入所有钥匙的所在处通过状态压缩记录每个点的钥匙情况第三步双端队列 BFS跑最短路分为此点有无钥匙和走下一步两个部分分别求解最短路记录以某种状态到达某点时的最短路AC代码#includeiostream#includecstdio#includealgorithm#includedeque#includecstring#includesetusingnamespacestd;constintN11,MN*N,E400,P110,INF0x3f3f3f3f;typedefpairint,intPII;intn,m,p,k;intst[M][P],dis[M][P];intne[E],h[M],e[E],w[E],idx;intG[N][N],key[M];setPIIedges;voidadd(inta,intb,intc){w[idx]c;e[idx]b;ne[idx]h[a];h[a]idx;return;}voidbuild(){intdx[]{-1,0,1,0},dy[]{0,1,0,-1};for(inti1;in;i){for(intj1;jm;j){for(intu0;u4;u){intvxidx[u],vyjdy[u];if(vx0||vxn||vy0||vym)continue;intaG[i][j],bG[vx][vy];if(edges.count({a,b})0)add(a,b,0);}}}return;}intbfs(){//哪个点什么状态memset(dis,INF,sizeofdis);dis[1][0]0;dequePIIq;q.push_back({1,0});while(!q.empty()){autonowq.front();q.pop_front();intnowunow.first,now_statenow.second;if(st[nowu][now_state])continue;st[nowu][now_state]true;//到了就可以直接输出if(nowun*m)returndis[nowu][now_state];//先判断这里有钥匙没if(key[nowu]){intne_statenow_state|key[nowu];if(dis[nowu][ne_state]dis[nowu][now_state]){dis[nowu][ne_state]dis[nowu][now_state];q.push_front({nowu,ne_state});}}//继续走for(intih[nowu];i!-1;ine[i]){intje[i];//有门且没有钥匙if(w[i]!(now_statew[i]1))continue;if(dis[j][now_state]dis[nowu][now_state]1){dis[j][now_state]dis[nowu][now_state]1;q.push_back({j,now_state});}}}return-1;}intmain(){memset(h,-1,sizeofh);scanf(%d%d%d%d,n,m,p,k);//给每个点赋值for(inti1,t1;in;i){for(intj1;jm;j){G[i][j]t;}}for(inti1;ik;i){intx1,y1,x2,y2,type;scanf(%d%d%d%d%d,x1,y1,x2,y2,type);intaG[x1][y1],bG[x2][y2];edges.insert({a,b});edges.insert({b,a});if(type){add(a,b,type);add(b,a,type);}}build();//建立其他边ints;scanf(%d,s);for(inti1;is;i){intx,y,id;scanf(%d%d%d,x,y,id);key[G[x][y]]|1id;}intansbfs();printf(%d,ans);return0;}
【洛谷题解/AcWing题解】洛谷P4011 孤岛营救问题/AcWing1131拯救大兵瑞恩
题目链接洛谷链接https://www.luogu.com.cn/problem/P4011AcWing链接https://www.acwing.com/problem/content/1133/涉及知识1.单源最短路2.双端队列广度优先搜索3.状态压缩动态规划和二进制的巧用思路分析第一部分题意的抽象——建图首先我们看到这一题不难想到这是一个限制条件较多的最短路那么我们就很自然地需要探索如何将本题的门、墙、钥匙等抽象成图、边等元素。图的基本元素是点和边因此我们也就围绕着两个元素展开。点点即当前麦克所在的地方。本题是以坐标的形式给到我们的这方便我们进行DFS或者BFS的转移但是不方便我们运用最短路算法的我们可以通过初始化赋值将每一个二维坐标转化为一维坐标并且在题中灵活运用这两种坐标。这一点会在之后的代码中有所体现同时每个点可能会有钥匙也就是说与经典最短路相比我们还需要考虑走到当前点时我们手中拿到的钥匙的情况。对于这一点我们可以借鉴状态压缩动态规划的思想将当前拿到的钥匙的情况用二进制数表示。特别注意本题中同一处地方可能会有多把钥匙因此我们在读入钥匙的坐标时不能简单地用等于而是用或操作合并。在宽搜走到要通过大门时则读取状态判断有无该类型的钥匙。在这里对于所涉及的二进制操作在状态压缩中的利用进行简单介绍至于每一种运算符的含义如果没有接触过请自行查阅资料有学过状压的可以略过1.简介在信息学的题目中我们常用二进制数来表示某一种状态比如动态规划中当前我们持有的物品。以本题为例我们想用二进制数表示当前我们持有x xx类型的钥匙本质上就是让二进制数的第x xx位变成 1 。在之后的读取中哪一位有 1就说明我们有哪一种钥匙。这也就解释了为什么开数组时的P PP要设置为1 10 110110(即等同于2 10 2^{10}210)因为共有 10 钟类型的钥匙每一种类型的钥匙我么可能持有状态为1可能没有状态为0两种情况。2.合并状态在二进制操作中我们采用或操作来合并两种状态。这里可以类比数学中的集合一个集合我们做并集运算其实就是把两个集合都有的元素通通放进来。或操作对两个二进制数的每一位进行判断只要其中有 1 位为 1结果便为 1也就是说只要我两种状态中有任意一种状态拥有这种类型的钥匙最后结果都会拥有。通过或操作我们就保证了当一个地方有多种类型的钥匙时结果都在取并集。3.读入状态以此题为例当我们拥有x xx类型的钥匙时读入便是让二进制数的第x xx位为 1。通过左移x xx位让第x xx位变成1得到一个新二进制数000..1...00 000..1...00000..1...001在第x xx位再用当前状态的二进制数和它做或运算即可得到新状态。4.读取状态读取状态便是希望取出第x xx位的数字判断其是否为1 11从而得出是否拥有x xx类型的钥匙。设当前状态为s ss则通过右移操作s x sxsx是在取出第x xx位s x 1 sx\1sx1就是在判断第x xx位是否为 1。边边即题中的门、墙和其他自由通行的路径。1.门和墙门我们可以直接读入将边权设定为其所属的类型即可。需要注意的是墙我们是不需要读入的因为我们是在做图论题只要不建边就不会有这条路也就不会通行了。2.自由通行的路径自由通行的路径相当于一扇不需要任何钥匙的“门”所以可以在读入完门和墙的数据之后用一个函数把自由通行的路径一次性初始化好设定为边权为 0 的边。为了防止给一扇门或者一堵墙所在的那条边也建上自由通行的路径我们可以在读入门和墙的时候用s e t setset统计已经出现的边。第二部分最短路的实现在本题中我们可以将捡到钥匙看作边权为 0 的边将朝四周走看作边权为 1 的边也就是两种可能的情况然后运用双端队列BFS即可得出走到瑞恩处的最短距离。需要注意的是此处的边权并非上面我们建边时的边权建边时我们只是用存储边权的数组存储了钥匙的类型而我们真正意义上的边权即我们跑最短路时走一步加的那个数字只是1。第三部分思路再梳理第一步读入n , m , p , k n,m,p,kn,m,p,k以及门和墙的数据统计所有已经出现的门和墙类型为门的边进行建边然后将其他可以自由通行的路径统一建边第二步读入所有钥匙的所在处通过状态压缩记录每个点的钥匙情况第三步双端队列 BFS跑最短路分为此点有无钥匙和走下一步两个部分分别求解最短路记录以某种状态到达某点时的最短路AC代码#includeiostream#includecstdio#includealgorithm#includedeque#includecstring#includesetusingnamespacestd;constintN11,MN*N,E400,P110,INF0x3f3f3f3f;typedefpairint,intPII;intn,m,p,k;intst[M][P],dis[M][P];intne[E],h[M],e[E],w[E],idx;intG[N][N],key[M];setPIIedges;voidadd(inta,intb,intc){w[idx]c;e[idx]b;ne[idx]h[a];h[a]idx;return;}voidbuild(){intdx[]{-1,0,1,0},dy[]{0,1,0,-1};for(inti1;in;i){for(intj1;jm;j){for(intu0;u4;u){intvxidx[u],vyjdy[u];if(vx0||vxn||vy0||vym)continue;intaG[i][j],bG[vx][vy];if(edges.count({a,b})0)add(a,b,0);}}}return;}intbfs(){//哪个点什么状态memset(dis,INF,sizeofdis);dis[1][0]0;dequePIIq;q.push_back({1,0});while(!q.empty()){autonowq.front();q.pop_front();intnowunow.first,now_statenow.second;if(st[nowu][now_state])continue;st[nowu][now_state]true;//到了就可以直接输出if(nowun*m)returndis[nowu][now_state];//先判断这里有钥匙没if(key[nowu]){intne_statenow_state|key[nowu];if(dis[nowu][ne_state]dis[nowu][now_state]){dis[nowu][ne_state]dis[nowu][now_state];q.push_front({nowu,ne_state});}}//继续走for(intih[nowu];i!-1;ine[i]){intje[i];//有门且没有钥匙if(w[i]!(now_statew[i]1))continue;if(dis[j][now_state]dis[nowu][now_state]1){dis[j][now_state]dis[nowu][now_state]1;q.push_back({j,now_state});}}}return-1;}intmain(){memset(h,-1,sizeofh);scanf(%d%d%d%d,n,m,p,k);//给每个点赋值for(inti1,t1;in;i){for(intj1;jm;j){G[i][j]t;}}for(inti1;ik;i){intx1,y1,x2,y2,type;scanf(%d%d%d%d%d,x1,y1,x2,y2,type);intaG[x1][y1],bG[x2][y2];edges.insert({a,b});edges.insert({b,a});if(type){add(a,b,type);add(b,a,type);}}build();//建立其他边ints;scanf(%d,s);for(inti1;is;i){intx,y,id;scanf(%d%d%d,x,y,id);key[G[x][y]]|1id;}intansbfs();printf(%d,ans);return0;}
