BFS——1495 非常可乐

1495 非常可乐

题目：

思路：

抽象BFS，把三个杯子的水量抽象成$(x,y,z)$的一个三维坐标，并按照题目要求修改拓展方式，在此基础上BFS即可(可以理解为在三维空间的BFS)。
拓展方式：

1. 对于一个坐标$(a,b,c)$一定要转移到类似于$(a?(N?b),N,c)$或者$(0,a+b,c)$等，其实就是模拟倒水过程，倒水过程要么倒水杯为空或者被倒水杯已满。

还是多补充一点：只要能抽象出表示状态的点和表示状态转移方式的边就可以搜索答案，这也是DFS和BFS用处广泛而强大的原因之一，经过抽象，可以解决很多的问题。

时间复杂度：

$O(S?N?M)$

AC代码：

事实上这题需要处理的地方还是有一些的，如果强行取模拟代码会又臭又长，而且还不容易调试，下面给出我的一份WA血泪教训(想偷懒结果寄了):

#include<bits/stdc++.h>typedef long long ll;const int N = 1e2+5,M = 2e4+10,INF = 0x3f3f3f3f,mod = 1e9+7;
struct Node{
    int x,y,z,step;
}que[N*N*N*3];int a,b,c;
bool book[N][N][N];void bfs()
{
    if(a&1){
    std::cout<<"NO\n";return;}int head = 0,tail = -1;que[++tail] = {
    a,0,0};book[a][0][0] = true;while(tail >= head){
    auto temp = que[head++];if((temp.x==a/2)+(temp.y==a/2)+(temp.z==a/2)==2){
    std::cout<<temp.step<<'\n';return;}if(temp.x){
    if(temp.x >= b - temp.y){
    if(!book[temp.x-(b-temp.y)][b][temp.z]){
    book[temp.x-(b-temp.y)][b][temp.z] = true;que[++tail] = {
    temp.x-(b-temp.y),b,temp.z,temp.step+1};}}else{
    if(!book[0][temp.y+temp.x][temp.z]){
    book[0][temp.x+temp.y][temp.z] = true;que[++tail] = {
    0,temp.x+temp.y,temp.z,temp.step+1};}}if(temp.x >= c - temp.z){
    if(!book[temp.x-(c-temp.z)][temp.y][c]){
    book[temp.x-(c-temp.z)][temp.y][c] = true;que[++tail] = {
    temp.x-(c-temp.z),temp.y,c,temp.step+1};}}else{
    if(!book[0][temp.y][temp.z+temp.x]){
    book[0][temp.y][temp.z+temp.x] = true;que[++tail] = {
    0,temp.y,temp.z+temp.x,temp.step+1};}}}if(temp.y){
    if(temp.y >= a - temp.x){
    if(!book[a][temp.y-(a-temp.x)][temp.z]){
    book[a][temp.y-(a-temp.x)][temp.z] = true;que[++tail] = {
    a,temp.y-(a-temp.x),temp.z,temp.step+1};}}else{
    if(!book[temp.x+temp.y][0][temp.z]){
    book[temp.x+temp.y][0][temp.z] = true;que[++tail] = {
    temp.x+temp.y,0,temp.z,temp.step+1};}}if(temp.y >= c - temp.z){
    if(!book[temp.x][temp.y-(c-temp.z)][c]){
    book[temp.x][temp.y-(c-temp.z)][c] = true;que[++tail] = {
    temp.x,temp.y-(c-temp.z),c,temp.step+1};}}else{
    if(!book[temp.x][0][temp.z+temp.y]){
    book[temp.x][0][temp.z+temp.y] = true;que[++tail] = {
    temp.x,0,temp.z+temp.y,temp.step+1};}}}if(temp.z){
    if(temp.z >= a - temp.x){
    if(!book[a][temp.y][temp.z-(a-temp.x)]){
    book[a][temp.y][temp.z-(a-temp.x)] = true;que[++tail] = {
    a,temp.y,temp.z-(a-temp.x),temp.step+1};}}else{
    if(!book[temp.x+temp.z][temp.y][0]){
    book[temp.x+temp.z][temp.y][0] = true;que[++tail] = {
    temp.x+temp.z,temp.y,0,temp.step+1};}}if(temp.z >= b - temp.y){
    if(!book[temp.x][b][temp.z-(b - temp.y)]){
    book[temp.x][b][temp.z-(b - temp.y)] = true;que[++tail] = {
    temp.x,b,temp.z-(b - temp.y),temp.step+1};}}else{
    if(!book[temp.x][temp.y+temp.z][0]){
    book[temp.x][temp.y+temp.z][0] = true;que[++tail] = {
    temp.x,temp.z+temp.y,0,temp.step+1};}}}}std::cout<<"NO\n";
}int main()
{
    
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
// std::cout.tie(nullptr);while(std::cin>>a>>b>>c){
    if(a==0&&b==0&&c==0)break;for(int i = 1 ; i <= a ; i++)for(int j = 1 ; j <= b ; j++)for(int k = 1 ; k <= c ; k++)book[i][j][k] = false;bfs();}
}

我们可以发现上面对于情况的讨论类似的代码是非常多的，所以我加了点处理，把所有情况用一份代码,缩短了代码：

#include<bits/stdc++.h>typedef long long ll;const int N = 1e2+10,M = 2e5+10,INF = 0x3f3f3f3f,mod = 1e9+7;
struct Node{
    int b[3],step;
}que[N*N*N];int a[3],pw[3];
bool book[N*N*N];void bfs()
{
    if(a[0]&1){
    std::cout<<"NO\n";return;}int tail = -1,head = 0;que[++tail] = {
    a[0],0,0,0};pw[0] = 1,pw[1] = 101,pw[2] = 101*101;book[a[0]] = true;while(tail >= head){
    auto temp = que[head++];if((temp.b[0]==a[0]/2)+(temp.b[1]==a[0]/2)+(temp.b[2]==a[0]/2)==2){
    std::cout<<temp.step<<'\n';return;}for(int i = 0 ; i <= 2 ; i++){
    for(int j = 1 ; j <= 2 ; j++){
    int x = i,y = (i+j)%3,z = (i+j+(j==1?1:-1))%3;if(!temp.b[x])continue;if(temp.b[x] >= (a[y]-temp.b[y])){
    int state = (temp.b[x]-(a[y]-temp.b[y]))*pw[x]+a[y]*pw[y]+temp.b[z]*pw[z];if(!book[state]){
    book[state] = true;tail++;que[tail].b[x] = temp.b[x]-(a[y]-temp.b[y]);que[tail].b[y] = a[y];que[tail].b[z] = temp.b[z];que[tail].step = temp.step + 1;}}else{
    int state = (temp.b[y]+temp.b[x])*pw[y]+temp.b[z]*pw[z];if(!book[state]){
    book[state] = true;tail++;que[tail].b[x] = 0;que[tail].b[y] = (temp.b[y]+temp.b[x]);que[tail].b[z] = temp.b[z];que[tail].step = temp.step + 1;}}}}}std::cout<<"NO\n";
}int main()
{
    
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
// std::cout.tie(nullptr);while(std::cin>>a[0]>>a[1]>>a[2]){
    if(a[0]==0||a[1]==0||a[2]==0)break;memset(book,false,sizeof book);bfs();}
}