有人会这题bfs吗？

常规
,
1

倒酒

时间限制：1s 空间限制：64M

题目描述:

给出三个杯子的体积，但杯子上没有刻度/指数。一开始第一个杯子是满的，另外两个是空的。请你判断是否可以将酒平均分配到某两杯中（都是整数），这两杯中的酒的体积为第一杯的一半。

输入格式:

三个杯子的体积（不超过150）。

输出格式:

将葡萄酒均匀地分配到某两个杯子的最少步骤。如果无法适应，则输出“NO”。

样例输入:

8 5 3

样例输出:

7

样例解释：

下面三个数字表示当前每个杯子里分别有多少酒，初始情况是：

8 0 0

接下来每一行代表一次操作：

3 5 0

3 2 3

6 2 0

6 0 2

1 5 2

1 4 3

4 4 0

总共7步。

2

一道有趣的题

时间：1s 空间：32M

题目描述：

你正在设计一个网格地图游戏，网格满足如下条件

1：恰好有一个出口

2：可能有一些门，门的标号为大写字母A-Z，每种门最多只有一个

3：可能有一些钥匙，钥匙的标号为小写字母a-z，每种钥匙只能打开对应的大写字母的门

4：可能有一些空地，空地的标号为小数点

5：可能有一些障碍，障碍不能经过

对于一个地图，你想要知道有多少的空地可以到达出口，为了使游戏显得不那么简单，你想要知道到达出口至少开一扇门的的空地有多少个

输入格式：

第一行输入两个整数n,m， (1≤n≤50)

接下来n行每行输入m个字符 (1≤m≤50)

‘.’ 代表空地

‘#’ 代表障碍

'*'代表出口

输出格式：

输出一个整数

样例输入1：

6 7 …#.A. .#B#.#. .#.#.#. .#.#.#. .#b#.#. a#…#*

样例输出1：

10

样例输入2：

3 5 a#a#* #…#. a…A.

样例输出2：

4

提示

这题也卡了：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,step;
};
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int b[26];
queue<node> q;
int c,d,i,j,ans=0,n,m,vis[55][55];
char a[55][55];
void dfs(){
    q.push( node{i,j,0});
    vis[i][j]=1;
    while(!q.empty()){
        for(int i=0;i<4;i++){
            int tx=q.front().x+dx[i];
            int ty=q.front().y+dy[i];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&vis[tx][ty]==0&&a[tx][ty]!='#'){
                if(tx==c&&ty==d){
                    ans++;
                    return ;
                }
                if(a[tx][ty]>='A'&&a[i][j]<='Z'){
                    if(b[(a[tx][ty]-'0')-64]==1){
                        q.push( node{tx,ty,q.front().step+1} );
                        vis[tx][ty]=1;
                    }
                }
                else if(a[tx][ty]>='a'&&a[i][j]<='b'){
                    q.push(node{tx,ty,q.front().step+1});
                    b[a[tx][ty]-96]+=1;
                    vis[tx][ty]=1;
                }
                else{
                    q.push( node{tx,ty,q.front().step+1} );
                    vis[tx][ty]=1;
                }
           }
        }
        q.pop();
    }
}
int main(){
    cin>>n>>m;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='*'){
                c=i,d=j;
            }
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(a[i][j]=='.'){
                for(int x=1;x<=n;x++){
                    for(int y=1;y<=m;y++){
                        vis[x][y]=0;
                    }
                }
                while(!q.empty()) q.pop();
                dfs();
            }
        }
    }
    cout<<ans*2;
}

这个代码好多地方是错的，我改了，改不出来（自己写的）……QwQ

3

一道有趣的题很毒瘤……（好多人都是c的）