博客搬家

题目链接 题意： 在迷宫内，J表示人，F表示火，火可能不止一处，但是人只有一个，火会向上下左右蔓延， 蔓延速度和人移动速度一至（每次一格，但是可以同时向四个方向）问是否可以成功逃出迷宫， 不能输出IMPOSSIBLE，能的画话输出最短路径。 题解： 每步先让火走–然后人走其他的路–就可以保证人不会被火烧了 先将火入队列最后将人入队列，走的时候判断下是人还是火，如果是人的话看看是否无路可走 注：也可以跑两次BFS，先跑火，再跑人，看人到当前格时间是否小于火的 AC代码： #include<cstdio> #include<qu...

题目链接 题意： 给你一个5*5的迷宫，0代表通路，1代表墙，找到从迷宫左上角到达右下角的最短路径，并输出路径。 题解： 先进行一遍BFS，得到vis数组，表示到该位置最少需要多少时间，然后从(4,4)位置倒着查路径， 查到符合的就直接break，防止重复 AC代码： #include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<queue> #include<stack> using...

题目链接 题意： 给你块地，有空地，也有草堆，让你选两个草堆进行点火，燃烧的草堆会引燃上下左右的相邻草堆， 每一次引燃花费1s时间，问你最少花多长时间把草堆都点着，如果做不到输出-1. 题解： 枚举图中所有草地，找到任意两块不一样的草地，然后bfs求出烧掉所有草的最短时间， 可以将两个初始状态都push进队列，这样就可以模拟两堆草同时燃烧的情况， 在bfs的过程中要判断是否烧完（即所有的草堆的点都要被访问过），如果烧完，就立即返回这点的距离， 就是以该状态枚举时，的最远距离，让后输出最远距离中最小的就是最终结果。 AC代码： #include<stdio....

题目链接 题意： 已知两堆牌s1和s2的初始状态， 其牌数均为c，按给定规则能将他们相互交叉组合成一堆牌s12， 再将s12的最底下的c块牌归为s1，最顶的c块牌归为s2，依此循环下去。 现在输入s1和s2的初始状态 以及 预想的最终状态s12 问s1 s2经过多少次洗牌之后，最终能达到状态s12，若永远不可能相同，则输出"-1"。 题解： 虽然归类于kuangbin搜索专题，但个人感觉模拟更好做，直接用map判重，进行模拟就可以。 如果出现了一个出现过的非目标串，则输出-1，因为此时操作是一个环无法到达目标串 AC代码： #includ...

题目链接 题意： 给定两个整数n和k，通过 n+1或n-1 或n*2 这3种操作，使得n==k，输出最少的操作次数 题解： 简单的对每个节点进行三个方向（三种走法）的BFS AC代码： #include<stdio.h> #include<string.h> #include<queue> #include<algorithm> using namespace std; typedef long long ll; const int maxn=100005; int vis[maxn]; int n,k; int ...

题目链接 题意： 给出两个四位数的素数a,b，求从a变到b最少要花几步？每一步只能将a中的一位改变，且改变后的数也要是素数。 题解： BFS枚举个位，十位，百位，千位变换的数，用素数表判断变换后是否为一个素数 AC代码： #include<stdio.h> #include<string.h> #include<queue> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e4+5; bool prime[...

题目链接 题意： 给一个三维图，可以前后左右上下6种走法，走一步1分钟，求最少时间（其实就是最短路） 题解： 最短路Bfs，和二维的基本一样，就是原来4个方向，现在6个方向，原来数组是二维，现在是三维，也相当于模板题了。 AC代码： #include<stdio.h> #include<cstring> #include<queue> #include<algorithm> using namespace std; typedef long long ll; const int maxn=50; struct no...

题目链接 题意： 给一个数n，让你找出一个只有1，0，组成的十进制数，要求是找到的数可以被n整除 题解： 用DFS是搜索 当前位数字 （除最高位固定为1），因为每一位都只有0或1两种选择 AC代码： #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; typedef unsigned long long ll; const int maxn=230; int n; bool ...

题目链接 题意： 给你一个棋盘，问在这个棋盘上放K个棋子，有多少种放法（每行每列只能有一个棋子） 题解： 对棋盘DFS搜索，每满足一种就ans++，基本是裸的 AC代码： #include<stdio.h> #include<string.h> typedef long long ll; const int maxn=17; char mp[maxn][maxn]; bool vis[maxn]; ll ans=0; int k,n; void dfs(int x,int y){ if(y>=k){ ans+...

题目链接 题意： 求2个点到KFC的距离之和，使其最小 题解： 可用2次BFS，分别求出2个点到各个KFC的最短距离，然后找出和最小的即可 AC代码： #include<stdio.h> #include<string.h> #include<iostream> #include<queue> #define inf 0xffffff using namespace std; const int N=210; int m,n,mark[N][N],dis[N][N][2],dir[4][2]={1,0, 0,1, ...

题目链接 题意： 就是给你一个地图，找出所有不相连（八个方向）的@组合有多少个 题解： 经典的DFS求联通块的题，和紫书上求油田一样，枚举每一个点进行DFS搜联通的@ AC代码： #include <stdio.h> #include<bits/stdc++.h> using namespace std; const int maxn=105; char mat[maxn][maxn]; int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}}; int ...

G - 穗乃果的考试 先对方块求一个二维前缀和，这样就相当于枚举前缀和中每一个小块的和了。 #include<stdio.h> #include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=998244353; char s[2200][2200]; ll a[2200][2200],sum[2200][2200]; int main(){ int n,m; scanf("%d%d",&n,&m); fo...

自闭感受 Camp最后一天了，不知不觉就过去了8天，突然对这段时光有点不舍，虽然自闭但却快乐着。 上午hls给我们讲了计数和概率，太无奈自己太菜只听懂了一点点，有点可惜了。ε=(´ο｀*)))唉。 下午训练果然和我预想的一样，最后一场应该是自闭场 （虽然天天自闭），一套题目下来，J题T了，A题队友被自己hack了，G题死怼一下午，从开始毫无思绪，到后面展开各种毛病。心态简直爆炸了 晚上和队友回去，看着路上6人的影子 （包括另外一队），突然感觉ACM是多么一件快乐并有意义的事情！还有9个月时间，加油Anoyer！ 上题解 G - 穗乃果的考试 先对方块求一个二维前缀...