2013年：第39级台阶
2014年：李白打酒，地宫取宝
2015年：牌型种数
2016年：方格填数，剪邮票
2018年：全球变暖
2019年：迷宫
2020年：走方格，七段码
2022年模拟赛：2021变1的最短操作数
2022年第一次模拟赛：15级台阶
2022年国赛：扩散
小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
请你利用计算机的优势，帮助小明寻找答案。
注意我们用的是dfs的思想，而非递归的思想（递归太容易绕进去了，博主也深受其害^^）
从地面开始向上走，有两种走法，上一层和上两层
只要我当前的台阶数不超过39，就可以继续深搜，否则的话，没必要继续下去
#include<iostream>
using namespace std;
int ans;
void dfs(int step,int n){
if(n > 39){
return;
}
if(step%2==0 && n==39){
ans++;
return;
}
dfs(step+1,n+1);
dfs(step+1,n+2);
}
int main(){
dfs(0,0);
cout << ans;
return 0;
}
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。 逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
从家门口开始走，有两种可能，遇到店和遇到花
只要李白遇到店不超过5次，遇到花不超过9次，最后一次已确定，就可以继续深搜
#include<iostream>
using namespace std;
int ans;
void dfs(int dian,int hua,int jiu){
if(dian > 5 || hua > 9){
return;
}
if(dian == 5 && hua == 9 && jiu == 1){
ans++;
return;
}
dfs(dian+1,hua,jiu*2);
dfs(dian,hua+1,jiu-1);
}
int main(){
dfs(0,0,2);
cout << ans;
return 0;
}
题目描述
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。数据格式
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)
接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。
例如，输入：
2 2 2
1 2
2 1
程序应该输出：
2
再例如，输入：
2 3 2
1 2 3
2 1 5
程序应该输出：
14
1.有三个参数，一个是坐标，一个是目前收集的宝物数目，一个是目前手里宝物中的最大价值
2.当(x,y)处的宝物的价值比我手里的最大价值大时，且我要拿，这是一种情况；剩下的就是另一种情况，虽然它比我手中的大但我不拿或我不能拿
3.当我到了终点，这时终点还没判断，终点需要单独判断，如果我已经拿了k件或者我拿了k-1件但终点的宝物价值比我手中的宝物价值大，我可以拿，也是k件
4.利用记忆化搜索简化时间复杂度，这里要注意因为我MaxV的初值设的是-1,而数组的下标不能有负数，所以我要加个偏移量1
#include<iostream>
#include<cstring>
using namespace std;
const int N = 60;
const long long MOD = 1e9+7;
int n,m,k;
int v[N][N];
long long mer[N][N][15][15];
long long dfs(int x,int y,int cnt,int MaxV){
if(x > n-1 || y > m-1 || cnt > k){
return 0;
}
if(x == n-1 && y == m-1){
if(cnt == k || (cnt == k-1 && v[x][y] > MaxV)){
return 1;
}
}
if(mer[x][y][cnt][MaxV+1] != -1){
return mer[x][y][cnt][MaxV+1];
}
long long ans = 0;
if(v[x][y] > MaxV){
ans += dfs(x + 1, y, cnt + 1, v[x][y]) + dfs(x, y + 1, cnt + 1, v[x][y]);
}
ans += dfs(x + 1, y, cnt, MaxV) + dfs(x, y + 1,cnt, MaxV);
return mer[x][y][cnt][MaxV+1] = ans%MOD;
}
int main(){
cin >> n >> m >> k;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
cin >> v[i][j];
}
}
memset(mer,-1,sizeof(mer));
cout << dfs(0,0,0,-1);
return 0;
}
小明被劫持到X赌城，被迫与其他3人玩牌。 一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。 这时，小明脑子里突然冒出一个问题： 如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？
我从第1种牌开始走，选i张（0<=i<=4），再去下一种牌的面前……，将第一种牌当成迷宫的入口，最后一种牌当成是迷宫的出口，到了迷宫的出口，如果此时手中的牌刚好是13张，就是一个方案
#include<iostream>
using namespace std;
int ans;
void dfs(int cnt,int sum){//cnt代表我走到第几点处了，sum表示我已经拿了几张牌了
if(cnt > 13 || sum > 13){
return;
}
if(cnt == 13){
if(sum == 13){
ans++;
}
return;
}
for(int i = 0;i <= 4;i++){
dfs(cnt+1,sum+i);//该点数我可以拿i张
}
}
int main(){
dfs(0,0);
cout << ans;
return 0;
}
如下的10个格子
填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
1.最多只用检查四个方向的数（左，上，左上，右上），因为这些格子中的数已经填好了，右，下，左下，右下这四个方向的数还没填
2.10个格子的初始值不能设为-1，因为如果第一个格子填的是0，他左边的格子是-1，相差1，但是它左边的格子不在10个格子内，第一个格子填0完全可以，但却检测不OK；所以我们设成-2
#include<iostream>
#include<cmath>
using namespace std;
int k[4][2] = {{-1,0},{0,-1},{-1,1},{-1,-1}};
int a[3][4];
bool vis[10];
int ans;
bool check(int x,int y,int n){
for(int i = 0;i < 4;i++){
int xx = x+k[i][0];
int yy = y+k[i][1];
if(xx>=0 && xx<3 && yy>=0 && yy<4){
if(abs(a[xx][yy]-n) == 1){
return false;
}
}
}
return true;
}
void dfs(int x,int y){
if(x == 2 && y == 3){
ans++;
return;
}
for(int i = 0;i < 10;i++){
if(!vis[i] && check(x,y,i)){
vis[i] = true;
a[x][y] = i;
if(y+1<=3){
dfs(x,y+1);
}else{
dfs(x+1,0);
}
//当0~9都不满足，这时就需要回溯了
a[x][y] = -2;
vis[i] = false;
}
}
}
int main(){
for(int i = 0;i < 3;i++){
for(int j = 0;j < 4;j++){
a[i][j] = -2;
}
}
dfs(0,1);
cout << ans;
return 0;
}
剪邮票如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。请你计算，一共有多少种不同的剪取方法。
1.这道题用并查集判断连通块有点麻烦，所以改用dfs判连通
2.利用全排列将所有情况列出再判断
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[] = {0,0,0,0,0,0,0,1,1,1,1,1};
int m[3][4];
int k[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
void dfs(int x,int y){
m[x][y] = 0;
for(int i = 0;i < 4;i++){
int xx = x + k[i][0];
int yy = y + k[i][1];
if(xx >= 0 && xx < 3 && yy >= 0 && yy < 4){
if(m[xx][yy] == 1){
dfs(xx,yy);
}
}
}
}
bool check(){
memset(m,0,sizeof(m));
for(int i = 0;i < 12;i++){
m[i/4][i%4] = a[i];
}
int cnt = 0;
for(int i = 0;i < 3;i++){
for(int j = 0;j < 4;j++){
if(m[i][j] == 1){
dfs(i,j);//消灭掉一个连通块
cnt++;
}
}
}
if(cnt == 1){
return true;
}
return false;
}
int main(){
int ans = 0;
do{
if(check()){
ans++;
}
}while(next_permutation(a,a+12));
cout << ans;
return 0;
}
题目描述
你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。【输入样例】
7
.......
.##....
.##....
....##.
..####.
...###.
.......【输出样例】
1
题目问的是：可以完全淹没的岛屿数！！！
isl：表示这块岛屿的陆地总数，is表示这块岛屿可以被淹没的陆地数
从未曾visited的陆地开始判断，每到达一块陆地，isl++并标记；如果这块陆地可以被淹没，is++
等到一块岛屿遍历完，开始判断isl和is是否相等，如果相等代表这块岛屿完全被淹没，如果不相等代表这块岛屿没有被完全淹没
错误原因：当成了水洼的数量那种题，但是这道题他不是问你有多少个岛屿，而是问你最终能淹没多少个岛屿！！！
#include<iostream>
using namespace std;
const int MAX_N = 1010;
char m[MAX_N][MAX_N];
int k[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
int N;
void dfs(int x,int y){
m[x][y] = '.';
for(int i = 0;i < 4;i++){
int xx = x + k[i][0];
int yy = y + k[i][1];
if(xx >= 0 && xx < N && yy >= 0 && yy < N){
if(m[xx][yy] == '#'){
dfs(xx,yy);
}
}
}
}
int main(){
cin >> N;
char c;
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++){
cin >> c;
m[i][j] = c;
}
}
int cnt = 0;
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++){
if(m[i][j] == '#'){
dfs(i,j);
cnt++;
}
}
}
cout << cnt;
return 0;
} 错误原因： 不是问你总共可以淹没多少陆地！！！
#include<iostream>
using namespace std;
const int MAX_N = 1010;
char m[MAX_N][MAX_N];
bool vis[MAX_N][MAX_N];
int k[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
int N;
int cnt;
bool check(int x,int y){
for(int i = 0;i < 4;i++){
int xx = x + k[i][0];
int yy = y + k[i][1];
if(xx >= 0 && xx < N && yy >= 0 && yy < N){
if(m[xx][yy] == '.'){
return true;
}
}
}
return false;
}
void dfs(int x,int y){
vis[x][y] = true;
if(check(x,y)){
cnt++;
}
for(int i = 0;i < 4;i++){
int xx = x + k[i][0];
int yy = y + k[i][1];
if(xx >= 0 && xx < N && yy >= 0 && yy < N){
if(!vis[xx][yy] && m[xx][yy] == '#'){
dfs(xx,yy);
}
}
}
}
int main(){
cin >> N;
char c;
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++){
cin >> c;
m[i][j] = c;
}
}
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++){
if(!vis[i][j] && m[i][j] == '#'){
dfs(i,j);
}
}
}
cout << cnt;
return 0;
} #include<iostream>
#include<queue>
using namespace std;
const int MAX_N = 1010;
int N;
char m[MAX_N][MAX_N];
int vis[MAX_N][MAX_N];
int k[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int ans,isl,is;
bool check(int x,int y){
for(int i = 0;i < 4;i++){
int xx = x + k[i][0];
int yy = y + k[i][1];
if(xx >= 0 && xx < N && yy >= 0 && yy < N){
if(m[xx][yy] == '.'){
return true;
}
}
}
return false;
}
void dfs(int x,int y){
vis[x][y] = true;
isl++;
if(check(x,y)){//如果它周围有海洋，证明它可以被淹没
is++;
}
//继续寻找下一个'#'
for(int i = 0;i < 4;i++){
int xx = x + k[i][0];
int yy = y + k[i][1];
if(xx >= 0 && xx < N && yy >= 0 && yy < N){
if(!vis[xx][yy] && m[xx][yy] == '#'){
dfs(xx,yy);
}
}
}
}
int main(){
cin >> N;
for(int i = 0;i < N;i++){
cin >> m[i];
}
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++){
if(m[i][j] == '#' && !vis[i][j]){//找到一块没有被遍历的岛屿
isl = is = 0;
dfs(i,j);
if(isl == is){
ans++;
}
}
}
}
cout << ans;
return 0;
}
问题描述
在平面上有一些二维的点阵。这些点的编号就像二维数组的编号一样。
从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。
现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。只能向右或者向下走。
注意，如果行号和列号都是偶数，不能走入这一格中。
问有多少种方案。
输入格式
输入一行包含两个整数 n，m。输出格式
输出一个整数，表示答案。样例输入1：
3 4样例输出1
2样例输入2：
6 6样例输出2
0数据范围
1 ≤ n ≤ 30, 1 ≤ m ≤ 30。
如果我走到的这个格子他超出了范围或它的行号和列号都是偶数，那么就没有必要再递归下去了
#include<iostream>
#include<cstring>
using namespace std;
const int N = 35;
int n,m;
long long mer[N][N];
long long dfs(int x,int y){
if(x > n || y > m || (x%2==0 && y%2==0)){
return 0;
}
if(x == n && y == m){
return 1;
}
if(mer[x][y] != -1){
return mer[x][y];
}
long long ans = 0;
ans += dfs(x,y+1) + dfs(x+1,y);
return mer[x][y] = ans;
}
int main(){
cin >> n >> m;
memset(mer,-1,sizeof(mer));
cout << dfs(1,1);
return 0;
}
题目描述
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如：b 发光，其他二极管不发光可以用来表达一种字符。
例如：c 发光，其他二极管不发光可以用来表达一种字符。
这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。
例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
dfs出所有的亮灯情况，再利用并查集判断所有亮灯情况的连通性
至于它是如何dfs出所有的亮灯情况的，我来画图说明：
#include<iostream>
#include<cstring>
using namespace std;
int v[8][8];//边
int vis[8];
int ans;
void dfs(int b){
vis[b] = 0;
for(int i = 1;i < 8;i++){
if(v[b][i] == 1 && vis[i] == 1){
dfs(i);
}
}
}
string toBinary(int i){
string s;
while(i){
if(i%2==1){
s += '1';
}else{
s += '0';
}
i/=2;
}
return s;
}
bool check(string s){
memset(vis,0,sizeof(vis));
for(int i = 0;i < s.length();i++){
if(s[i] == '1'){
vis[i+1] = 1;
}
}
int cnt = 0;
for(int i = 1;i < 8;i++){
if(vis[i] == 1){
dfs(i);
cnt++;
}
}
if(cnt == 1){
return true;
}
return false;
}
int main(){
v[1][2] = v[1][6] = 1;
v[2][1] = v[2][3] = v[2][7] = 1;
v[3][2] = v[3][7] = v[3][4] = 1;
v[4][3] = v[4][5] = 1;
v[5][4] = v[5][7] = v[5][6] = 1;
v[6][1] = v[6][5] = v[6][7] = 1;
v[7][2] = v[7][6] = v[7][3] = v[7][5] = 1;
for(int i = 1;i < (1<<7);i++){
string s = toBinary(i);
if(check(s)){
ans++;
}
}
cout << ans;
return 0;
}#include<iostream>
using namespace std;
int v[8][8];
int f[8];
bool vis[8];
int ans;
int find(int x){
if(x != f[x]){
return find(f[x]);
}
return f[x];
}
void dfs(int n){
if(n == 8){
for(int i = 1;i <= 7;i++){
f[i] = i;
}
for(int i = 1;i <= 7;i++){
for(int j = 1;j <= 7;j++){
if(v[i][j] == 1 && vis[i] && vis[j]){
if(find(i) != find(j)){
f[find(i)] = find(j);
}
}
}
}
int cnt = 0;
for(int i = 1;i <= 7;i++){
if(vis[i] && i == f[i]){
cnt++;
}
}
if(cnt == 1){
ans++;
}
return;
}
//打开第i个灯，从第i个灯开始dfs
vis[n] = true;
dfs(n+1);
//从第i个灯开始的所有情况已经遍历完，就将他熄灭 ，再从第i+1个灯开始dfs
vis[n] = false;
dfs(n+1);
}
int main(){
v[1][2] = v[1][6] = 1;
v[2][1] = v[2][3] = v[2][7] = 1;
v[3][2] = v[3][7] = v[3][4] = 1;
v[4][3] = v[4][5] = 1;
v[5][4] = v[5][7] = v[5][6] = 1;
v[6][1] = v[6][5] = v[6][7] = 1;
v[7][2] = v[7][6] = v[7][3] = v[7][5] = 1;
dfs(1);
cout << ans;
return 0;
}
小蓝要上一个楼梯，共 15 级台阶。
小蓝每步可以上 1 级台阶，也可以上 2 级、3 级或 4 级，再多就没办法一步走到了。
每级台阶上有一个数值，可能正也可能负。每次走到一级台阶上，小蓝的得分就加上这级台阶上的数值。台阶上的数值依次为: 1, 2, 1, 1, 1, 1, 5, 5, 4, -1, -1, -2, -3, -1, -9。
小蓝希望不超过 6 步走到台阶顶端，请问他得分的最大值是多少?
注意，小蓝开始站在地面上，地面没有分值。他最终要走到台阶顶端，所以最终一定会走到数值为 -9 的那级台阶，所以 -9 一定会加到得分里面。
将地面当成是迷宫的起点，第15级台阶当成是迷宫的终点，到了迷宫的终点，如果此时步数刚好不超过6，就是一个新的结果，每获得一个新的结果就更新最大值
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int ans = -INF;
int v[] = {0,1,2,1,1,1,1,5,5,4,-1,-1,-2,-3,-1,-9};
void dfs(int n,int step,int Max){//表示上到第n级台阶，走了step步的得分的最大值
if(n > 15 || step > 6){
return;
}
if(n == 15){
if(step <= 6){
ans = max(ans,Max);
}
return;
}
for(int i = 1;i <= 4;i++){
dfs(n+i,step+1,Max+v[n+i]);
}
}
int main(){
dfs(0,0,0);
cout << ans;
return 0;
}
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务 必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt， 内容与下面的文本相同）
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
每一步都按照D，L，R，U的方向走，最终得到的答案一定是字典序最小的
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
char m[30][51];
bool vis[30][51];
int k[4][2] = {{1,0},{0,-1},{0,1},{-1,0}};
char d[] = {'D','L','R','U'};
struct point{
int x,y;
string s;
point(int _x,int _y,string _s){
x = _x;
y = _y;
s = _s;
}
};
void bfs(int x,int y){
queue<point> q;
vis[x][y] = true;
q.push(point(x,y,""));
while(!q.empty()){
point p = q.front();
q.pop();
if(p.x == 29 && p.y == 49){
cout << p.s;
break;
}
for(int i = 0;i < 4;i++){
int xx = p.x + k[i][0];
int yy = p.y + k[i][1];
if(xx >= 0 && xx < 30 && yy >= 0 && yy < 50){
if(!vis[xx][yy] && m[xx][yy] == '0'){
q.push(point(xx,yy,p.s+d[i]));
vis[xx][yy] = true;
}
}
}
}
}
int main(){
char c;
for(int i = 0;i < 30;i++){
for(int j = 0;j < 50;j++){
cin >> c;
m[i][j] = c;
}
}
bfs(0,0);
return 0;
}
有一个整数 A=2021，每一次，可以将这个数加 1 、减 1 或除以 2，其中除以 2 必须在数是偶数的时候才允许。
例如，2021 经过一次操作可以变成 2020、2022。
再如，2022 经过一次操作可以变成 2021、2023 或 1011。
请问，2021 最少经过多少次操作可以变成 1。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
bool vis[2022];
struct point{
int x,cnt;
point(int _x,int _cnt){
x = _x;
cnt = _cnt;
}
};
void bfs(int x){
queue<point> q;
q.push(point(x,0));
vis[x] = true;
while(!q.empty()){
point p = q.front();
q.pop();
if(p.x == 1){
cout << p.cnt;
break;
}
if(!vis[p.x+1]){
q.push(point(p.x+1,p.cnt+1));
}
if(!vis[p.x-1]){//这里不需要担心p.x-1会出现负数的情况，因为如果p.x==1，那么他已经输出了
q.push(point(p.x-1,p.cnt+1));
}
if(p.x%2==0 && !vis[p.x/2]){
q.push(point(p.x/2,p.cnt+1));
}
}
}
int main(){
bfs(2021);
return 0;
}
小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。
小蓝在画布上首先点了一下几个点：(0 , 0), (2020 , 11), (11 , 14), (2000 , 2000)。
只有这几个格子上有黑色，其它位置都是白色的。
每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它
就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色
（如果原来就是黑色，则还是黑色）。
请问，经过 2020 分钟后，画布上有多少个格子是黑色的。
因为数组的下标不能是负数，所以需要加一个偏移量3000
#include<iostream>
#include<queue>
using namespace std;
int m[10000][10000];
bool vis[10000][10000];
int k[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
struct point{
int x,y,min;
point(int _x,int _y,int _min){
x = _x;
y = _y;
min = _min;
}
};
void bfs(){
queue<point> q;
q.push(point(3000,3000,0));
q.push(point(5020,3011,0));
q.push(point(3011,3014,0));
q.push(point(5000,5000,0));
vis[3000][3000] = 1;
vis[5020][3011] = 1;
vis[3011][3014] = 1;
vis[5000][5000] = 1;
int cnt = 4;
while(!q.empty()){
point p = q.front();
q.pop();
if(p.min == 2020){
cout << cnt;
break;
}
for(int i = 0;i < 4;i++){
int xx = p.x + k[i][0];
int yy = p.y + k[i][1];
if(m[xx][yy] == 0 && !vis[xx][yy]){
q.push(point(xx,yy,p.min+1));
vis[xx][yy] = 1;
cnt++;
}
}
}
}
int main(){
m[3000][3000] = 1;
m[5020][3011] = 1;
m[3011][3014] = 1;
m[5000][5000] = 1;
bfs();
return 0;
} 我有一个随机大小的散列，它可能有类似"100"的值，我想将其转换为整数。我知道我可以使用value.to_iifvalue.to_i.to_s==value来做到这一点，但我不确定我将如何在我的散列中递归地做到这一点，考虑到一个值可以是一个字符串，或一个数组(哈希或字符串)，或另一个哈希。 最佳答案 这是一个非常简单的递归实现(尽管必须同时处理数组和散列会增加一些技巧)。deffixnumifyobjifobj.respond_to?:to_i#IfwecancastittoaFixnum,doit.obj.to_ielsifobj
我经常迷上ruby的一件事是递归模式。例如，假设我有一个数组，它可能包含无限深度的数组作为元素。所以，例如:my_array=[1,[2,3,[4,5,[6,7]]]]我想创建一个方法，可以将数组展平为[1,2,3,4,5,6,7]。我知道.flatten可以完成这项工作，但这个问题是作为我经常遇到的递归问题的一个例子-因此我试图找到一个更可重用的解决方案。简而言之-我猜这种事情有一个标准模式，但我想不出任何特别优雅的东西。任何想法表示赞赏 最佳答案 递归是一种方法，它不依赖于语言。您在编写算法时要考虑两种情况:再次调用函数的情
我有这个ruby代码:defget_sumnreturn0ifn似乎正在为999之前的值工作。当我尝试9999时，它给了我这个:stackleveltoodeep(SystemStackError)所以，我添加了这个:RubyVM::InstructionSequence.compile_option={:tailcall_optimization=>true,:trace_instruction=>false}但什么也没发生。我的ruby版本是:ruby1.9.3p392(2013-02-22revision39386)[x86_64-darwin12.2.1]我还增加了机器的堆栈大
构建一个深度优先的网络蜘蛛，这意味着它将访问第一页上的所有链接，然后转到每个链接，并访问所有第二页上的链接...你应该使用递归吗？我发现这是CPU密集型的。defrecursion()linkz_on_first_page.eachdo|link|recursion(link)endendrecursion(firstpage) 最佳答案 绝对不是，由于万维网的实际性质，您很快就会遇到问题。当您访问带有主导航部分的网站时，每个页面都链接到其他页面，您就进入了一个无限循环。您可以跟踪您处理了哪些链接，但即便如此，递归循环并不真正适合万
例如，如果我有YAML文件en:questions:new:'NewQuestion'other:recent:'Recent'old:'Old'这最终会变成一个json对象，例如{'questions.new':'NewQuestion','questions.other.recent':'Recent','questions.other.old':'Old'} 最佳答案 由于问题是关于在Rails应用程序上使用YAML文件进行i18n，因此值得注意i18ngem提供了一个辅助模块I18n::Backend::Flatten完全像
目录前言： 一、ASC分析代码实现二、 卡片分析代码实现三、 直线分析代码实现四、货物摆放分析代码实现小结：前言： 在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。 一、ASC 已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析 这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy
我有这两个gcd函数的实现:defgcd1(a,b)ifa==baelsifa>bif(a%b)==0belsegcd1(a%b,b)endelseif(b%a)==0aelsegcd1(a,b%a)endendenddefgcd2(a,b)if(a==b)returnaelsifb>amin,max=a,belsemin,max=b,aendwhile(max%min)!=0min,max=max%min,minendminend函数gcd1是尾递归的，而gcd2使用while循环。我已经验证rubinius通过对阶乘函数进行基准测试来执行TCO，只有阶乘函数基准测试显示递归版本和迭
我想显示一个由gem祖先管理的类别树。我想使用一个助手，它会递归地遍历树并一个一个地返回类别，暂时没有html标签或内容。moduleCategoriesHelperdefdisplay_tree(category)ifcategory.has_children?category.children.eachdo|sub_category|display_tree(sub_category)puts(sub_category.name)#tocheckifitgoeshereendendcategory.nameendendcategory参数是根类别之一。它应该返回什么？在网页中:它仅
我有一个grammarfile对于我正在尝试构建的一种新的通用编程语言。我正在努力使该语言健壮且易于使用(它深受Ruby等启发)，为此我引入了一些左递归规则。我看到一些例子似乎表明了以下左递归规则:rulel_recursel_recurse/'somethingelse'end可以通过将其更改为非左递归:ruler_recurse'somethingelse'/r_recurseend对我来说，这看起来会有不同的问题并且仍然会失败。我是对的，还是这会“奏效”？我试图(查找和)消除的特定左递归可以在这个grammarfile中找到.我不确定哪些规则受到影响，但至少somewerepoi
我希望我的项目的顶级Rakefile使用树中更深的rakefile来构建东西；即顶层rakefile说明如何构建项目(大图)，而较低层的rakefile说明如何构建特定模块(本map片)。当然有一组共享的配置，用于在任务之间共享时执行的详细信息:所以它主要是关于保持对需要构建的内容的描述，尽可能接近正在构建的源。例如。/Source/Module/code.foo和cie应该使用/Source/Module/Rakefile中的指令构建；并且/Rakefile了解模块之间的依赖关系。我不关心它是否使用多个rake进程(ala递归make)，或者只是创建单独的构建环境。无论哪种方式，它都