牛客算法竞赛入门课第五节习题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] == &#39;*&#39;)
        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] == &#39;*&#39;) 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

http://oj.ecustacm.cn/problem.php?id=1393

思路：相当于一个圈，每个一个单位长度有一个点，每次可以一次走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;
}

钥匙：记忆化搜索

https://ac.nowcoder.com/acm/contest/8582/G

思路：直接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;
}