目录

全排列

catch that cow

红与黑

---

全排列

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入：

3

输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

开两个数组，一个存放状态（即放没放这个数），另一个存放数字

如果搜完了

 if(u>n){for(int i = 1;i <= n;i ++){std::cout<<path[i]<<" ";}std::cout<<"\n";

如果没搜完，继续向下一层搜索

else {for (int i = 1; i <= n; i++) {if (state[i] == 0) {path[u] = i;state[i] = 1;dfs(u + 1);path[u] = 0;state[i] = 0;}}}

完整代码

#include <bits/stdc++.h>
const int N = 10;
int n;
int state[N];//看是否标记过
int path[N];//放数
void dfs(int u)//层数
{if (u > n) {for (int i = 1; i <= n; i++) {std::cout << path[i] << " ";}std::cout << "\n";} else {for (int i = 1; i <= n; i++) {if (state[i] == 0) {path[u] = i;//这一层放istate[i] = 1;//这一层已经搜过了dfs(u + 1);//向下一层搜索path[u] = 0;//回溯state[i] = 0;//回溯}}}
}
int main() {std::cin >> n;dfs(1);return 0;
}

catch that cow

https://www.luogu.com.cn/problem/P1588

有三种不同的走法，+1，-1，*2

多组输入，首先进行一个队列清空操作，初始化数组，农夫的起点为0，起点入队

当队列不空时（！q.empty()）取出队头元素，弹出队头元素，

如果抓住了奶牛，输出，结束

如果没有抓住，判断三种情况，如果能走（没有越界），步数+1，入队

完整代码

#include <bits/stdc++.h>
std::queue<int> q;
const int maxn=1e5+10;
int dis[maxn];//走了多少步
void bfs(int s,int y)
{int x;while(!q.empty())//多组输入常规清空操作{q.pop();}memset(dis,0x5a5b5c4f,sizeof(dis));dis[s]=0;//农夫的起点为0q.push(s);//入队列while(!q.empty()){x=q.front();q.pop();if(x==y)//抓住了奶牛{std::cout<<dis[y]<<"\n";return;}if(x+1<=maxn&&dis[x+1]==dis[0]){dis[x+1]=dis[x]+1,q.push(x+1);}if(x-1>0&&dis[x-1]==dis[0]){dis[x-1]=dis[x]+1,q.push(x-1);}if(x*2<=maxn&&dis[x*2]==dis[0]){dis[x*2]=dis[x]+1,q.push(x*2);}}
}
int main()
{int t;std::cin >> t;int x,y;while(t --){std::cin >> x >> y;bfs(x,y);}return 0;
}

红与黑

红与黑 - 计蒜客 (jisuanke.com)

首先创建一个结构体类型的队列，对初始值进行入队操作

然后判断，如果是黑瓷砖，ans++,再判断周围的

完整代码

//r是行，c是列
#include <bits/stdc++.h>
struct node
{int r,c;
};
int n,m;
char g[100][100];//存图
bool vis[100][100]{};//{}表示这个数组都初始化为0
int init_r,init_c,ans;
void bfs()
{std::queue<node> q;//创建一个结构体的队列q.push({init_r,init_c});int rr[4]={-1,1,0,0};int cc[4]={0,0,-1,1};//搜索顺序while(!q.empty())//队列不空{node tmp=q.front();q.pop();int cur_r=tmp.r,cur_c=tmp.c;//当前的位置，currentlyif(g[cur_r][cur_c]=='.'){ans++;}for(int i = 0;i < 4;i ++){int next_r=cur_r+rr[i];int next_c=cur_c+cc[i];//下一个位置 nextif(next_r>=1&&next_r<=n&&next_c>=1&&next_c<=m&&!vis[next_r][next_c]&&g[next_r][next_c]=='.'){q.push({next_r,next_c});vis[next_r][next_c]=true;}}}
}
int main()
{std::cin >> m >> n;for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){std::cin >> g[i][j];if(g[i][j]=='@'){init_r=i;init_c=j;}}}bfs();std::cout<<ans+1<<"\n";return 0;
}