牛客算法竞赛入门课第五节习题dfs/bfs
Jelly
https://ac.nowcoder.com/acm/problem/201613
https://ac.nowcoder.com/acm/problem/201613
##三维bfs
#include <bits/stdc++.h>
#include <iostream>
const int Max = 100 * 100 * 100 + 5;
#define LL long long
const int mod = 1e9+7;
//const int inx = INT_MAX;
using namespace std;
// srand(time(NULL));
// m = rand() % 1000 + 1;
//定义i i(A) i+n i+n(B) i+n+n i+n+n(C)
//bitset<Max>s,q;
typedef struct s{
int x,y,z;
}s;
queue<s>q;
int dir[105][105][105];
char ch[105][105][105];
int dis[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int n;
bool check(int x,int y,int z)
{
if(x < 1 || y < 1 || z < 1 || x > n || y > n || z > n || dir[x][y][z] != 0 || ch[x][y][z] == '*')
return false;
else return true;
}
void bfs()
{
dir[1][1][1] = 1;
int x1,y1,z1;
s t;
t.x = 1;
t.y = 1;
t.z = 1;
q.push(t);
while(!q.empty()){
t = q.front();
q.pop();
for(int i = 0; i < 6; i++){
x1 = t.x + dis[i][0];
y1 = t.y + dis[i][1];
z1 = t.z + dis[i][2];
if(check(x1,y1,z1)){
dir[x1][y1][z1] = dir[t.x][t.y][t.z] + 1;
q.push((s){x1,y1,z1});
}
}
}
}
int main()
{
int i,j,k;
cin >> n;
getchar();
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
for(k = 1; k <= n; k++){
cin >> ch[i][j][k];
}
}
}
bfs();
if(ch[n][n][n] == '*') cout << -1;
else cout << dir[n][n][n];
return 0;
}
幸运数字
https://ac.nowcoder.com/acm/problem/15291
思路：先用dfs分别找出以4开头的和以7开头的数字存放到数组里面，又因为next[x]表示大于等于x的数字，而x，x+1,x+2...直到下一个数字之间的和是可以直接算到的，sum=(a[i] - a[i-1] + 1)*a[i].注意l和r同时小于第一个大于等于l的数。
#include <bits/stdc++.h>
#include
#include
#include <stdio.h>
const int Max = 100 * 100 * 100 + 5;
#define LL long long
LL mod = 1e9+7;
const int INF = 1e5;
//const int inx = INT_MAX;
using namespace std;
// srand(time(NULL));
// m = rand() % 1000 + 1;
//定义i i(A) i+n i+n(B) i+n+n i+n+n(C)
//bitsets,q;
//int a[100],n;
LL nex[100005],t = 2;
void dfs(LL n)
{
if(n > 1e9) return;
if(n > 10) nex[t++] = n;
dfs(n10+4);
dfs(n10+7);
}
int main()
{
nex[0] = 4,nex[1] = 7;
dfs(4);
dfs(7);
nex[t] = 4444444444;
sort(nex,nex+t+1);
LL l,r,xb;
cin >> l >> r;
LL sum = 0,s,i;
for(i = 0; i <= t; i++){
if(nex[i] >= l){
xb = i;
break;
}
}
if(r <= nex[xb]){
sum += (r - l + 1) * nex[xb];
}
else{
for(i = xb; i <= t; i++){
if(i == xb){
sum += (nex[xb] - l + 1) * nex[i];
}
else if(nex[i] > r){
sum += (r - nex[i - 1]) * nex[i];
break;
}
else{
sum += (nex[i] - nex[i - 1]) * nex[i];
}
}
}
cout << sum;
return 0;
}
递归打印全排列和集合的所有子集
全排列
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
using namespace std;
//void print(char a[])
//{
// printf("%d %c\n",strlen(a),a[2]);
//}
int a[5] = {1,2,3,4,5};
void Perm(int d,int n)
{
if(d == n){
for(int i = 0; i < 5; i++){
cout << a[i] << " ";
}
cout << endl;
return;
}
for(int i = d; i <= n; i++){
swap(a[d],a[i]);//将d个数依次与后面的数换
Perm(d+1,n);//求d+1 - n的全排列。
swap(a[d],a[i]);
}
}
int main()
{
int n,x,y,v,t;
Perm(0,4);
return 0;
} 集合的子集
递归法
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
using namespace std;
//选2时 选3 即为2 3， 不选2 即为 2.
bool a[10];
void dfs(int n,int num)
{
if(num > n){
for(int i = 1; i <= n; i++) if(a[i] == true) cout << i << " ";
cout << endl;
return;
}
a[num] = true;//选第num个数
dfs(n,num+1);
a[num] = false;//不选第num个数
dfs(n,num+1);
}
int main()
{
int n,x,y,v,t;
scanf("%d",&n);
dfs(n,1);
return 0;
}
二进制枚举法：
长度为n的集合的子集有2的n次方个子集。
题目：巅峰赛第11场 https://ac.nowcoder.com/acm/contest/6912/B
/**
* struct Point {
* int x;
* int y;
* };
*/
class Solution {
public:
/**
* 返回新集合的种类数
* @param n int整型 集合大小
* @param m int整型 限制数量
* @param limit Point类vector 不能同时出现的(u,v)集合
* @return int整型
*/
int a[25];
int cal(int n,int m,vector<Point>& limit){
int ans = 0;
for(int i = 0; i < (1 << n); i++){
memset(a,0,sizeof(a));
for(int j = 0; j < n; j++){
if(i & (1 << j)) a[j+1] = 1;
}
int cnt = 0,u,v;
for(int k = 0; k < m; k++){
u = limit[k].x;
v = limit[k].y;
if(a[u] && a[v]){
cnt++;
break;
}
}
if(!cnt) ans++;
}
return ans;
}
int solve(int n, int m, vector<Point>& limit) {
// write code here
int ans = cal(n,m,limit);
return ans;
}
}; 第九届蓝桥杯国赛-调手表：bfs
思路：相当于一个圈，每个一个单位长度有一个点，每次可以一次走1步走，或者一次走k长步，走过的点不能再走，问到每个点的步数最多是多少步。
用bfs很巧妙的可以解决。到达某个点，下一步可以走一步，或k长步，这不就是相当于在矩阵中可以往上下左右四个方向走类似吗？而我们又知道不考虑距离，只考虑一步长度的话，用bfs可以找出到每个点的最短路，先到就是最短。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9;
const ll ds = 1e15+7;
//const double p = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
int num[100005];
int main()
{
int n,k;
cin >> n >> k;
memset(num,-1,sizeof num);
num[0] = 0;
queue<int>q;
q.push(0);
while(!q.empty()){
int s = q.front();
q.pop();
if(num[(s+1)%n] == -1){
num[(s+1)%n] = num[s]+1;
q.push((s+1)%n);
}
if(num[(s+k)%n] == -1){
num[(s+k)%n] = num[s]+1;
q.push((s+k)%n);
}
}
int ans = 0;
for(int i = 0; i < n; i++){
ans = max(ans,num[i]);
}
cout << ans;
return 0;
} 钥匙：记忆化搜索
思路：直接dfs肯定不行，所有采用记忆化搜索，dp[i][j][k]表示第i个槽的前j个槽深序列为sum的二进制。但如果是用dp[pre][cur][l],第l个的前一个是pre，第l个是cur，来保存好像答案不对，也不知道为什么......。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll ans;
int a[55],n,j;
set<int>s;
ll dp[35][35][155];
int pd(int x)
{
int cnt = 0;
while(x){
if(x & 1) cnt++;
x >>= 1;
}
return cnt;
}
ll dfs(int l,int pre,int sum)
{
if(l >= n){
if(pd(sum) >= 3){
return 1;
}
return 0;
}
if(dp[l][pre][sum] != -1) return dp[l][pre][sum];
ll ans = 0;
for(int i = 1; i <= 6; i++){
if(l && abs(pre-i) >= 5) continue;
if((sum >> i) & 1) ans += dfs(l+1,i,sum);
else ans += dfs(l+1,i,sum+(1<<i));
}
dp[l][pre][sum] = ans;
return ans;
}
int main()
{
while(cin >> n){
memset(dp,-1,sizeof(dp));
cout << dfs(0,0,0) << endl;
}
return 0;
} 逃出机房
https://ac.nowcoder.com/acm/contest/10293/A 思路：如果zyj到达某个出口的时间比hl短，那么就可以逃出，bfs求出出口到两个人的最短距离即可。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ull res = 233;
using namespace std;
struct node{
int x,y,len;
node(int a,int b,int c){
x = a;
y = b;
len = c;
}
};
char a[15][15];
int d[15][15],vis[15][15];
int z1,z2,h1,h2,n,m;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
bool check(int x,int y)
{
if(x <= 0 || y > m || x > n || y <= 0) return false;
return true;
}
bool bfs(int x,int y)
{
memset(vis,0,sizeof(vis));
memset(d,0,sizeof(d));
queue<node>q;
q.push(node(x,y,1));
vis[x][y] = 1;
d[x][y] = 0;
int h,z;
h = z = 0;
while(!q.empty()){
node s = q.front();
q.pop();
vis[s.x][s.y] = 1;
if(s.x == z1 && s.y == z2) z = s.len;
if(s.x == h1 && s.y == h2) h = s.len;
// cout << 1 << endl;
for(int i = 0; i < 4; i++){
int x1,y1;
// cout << i << endl;
x1 = s.x + dir[i][0];
y1 = s.y + dir[i][1];
if(!check(x1,y1) || vis[x1][y1] || a[x1][y1] == '#') continue;
q.push(node(x1,y1,s.len+1));
}
}
return z < h;
}
int main()
{
memset(d,0,sizeof(d));
cin >> n >> m;
getchar();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
if(a[i][j] == 'Z') z1 = i,z2 = j;
if(a[i][j] == 'H') h1 = i,h2 = j;
}
}
int flag = 0;
for(int i = 1; i<= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] == '@'){
if(bfs(i,j)) flag = 1;
}
}
}
if(flag) printf("give me northeast chicken rice and milk tea TOMORROW!");
else printf("give me northeast chicken rice and milk tea!");
return 0;
}
