dfs/bfs练习题

母亲的牛奶

题目链接：母亲的牛奶

步骤：

1. 分析题目，找出总共有多少种状态，从而得出队列数组的内存空间
2. 每种状态相当于一个点，状态与状态之间的转变相当于一条边
3. bfs遍历，将每种状态都存在队列中。

#include <bits/stdc++.h>

using namespace std;

//A，B，C最大为20升
//状态个数为20^3
const int N = 21;
int A,B,C;
struct node{
    int a,b,c;
}q[N*N*N]; //关键点，队列数组q有N^3个状态
 
int hh=0,tt=-1;

bool st[N][N][N];
int s[N]; //记录当 A桶是空的时候，C桶中可能包含多少升牛奶

void insert(int a, int b, int c){
    if(!st[a][b][c]){
        q[++tt] = {a,b,c};
        st[a][b][c] = true;
    }
}
void bfs(){
    q[++tt] = {0,0,C};
    st[0][0][C] = true;
    while(hh <= tt){
        node t = q[hh];
        hh++;
        int a = t.a; int b = t.b; int c = t.c;
        //由当前状态可以得到2*3 = 6 种状态
        //从A开始转移
        insert(a-min(a,B-b), min(a+b,B), c);
        insert(a-min(a,C-c), b, min(a+c,C));
        //从B开始转移
        insert(min(a+b,A), b-min(b,A-a), c);
        insert(a, b-min(b,C-c), min(b+c,C));
        //从C开始转移
        insert(min(a+c,A), b, c-min(c,A-a));
        insert(a, min(b+c,B), c-min(c,B-b));
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> A >> B >> C;
    bfs();
    int cnt = 0;
    for(int i=0;i<hh;i++){
        if(q[i].a == 0){
            s[cnt] = q[i].c;
            cnt++;
        }
    }
    sort(s,s+cnt);
    for(int i=0;i<cnt;i++){
        cout << s[i] << " ";
    }
    return 0;
}

小红走矩阵(bfs)

小红走矩阵

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;

const int N = 1e3+10;
int n,m;
char g[N][N];
int dist[N][N];

int ax[4] = {0,0,1,-1};
int ay[4] = {1,-1,0,0};

queue<PII> q;

int bfs(){
    q.push({0,0});
    dist[0][0] = 0;
    while(!q.empty()){
        PII t = q.front();
        q.pop();
        //该处永远是循环4次
        for(int i=0;i<4;i++){
            int x = t.first + ax[i]; int y = t.second + ay[i];
            if(x>=0&&x<n&&y>=0&&y<m && g[x][y] != g[t.first][t.second] && dist[x][y] == -1){
                q.push({x,y});
                dist[x][y] = dist[t.first][t.second] + 1;
            }
        }
    }
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         cout << dist[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    return dist[n-1][m-1];
}

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> g[i][j];
        }
    }
    memset(dist,-1,sizeof(dist));
    cout << bfs();
    return 0;
}

老师的签到