题目链接:http://ac.jobdu.com/problem.php?pid=1457
详解链接:https://github.com/zpfbuaa/JobduInCPlusPlus
参考代码:
//
// 1457 非常可乐.cpp
// Jobdu
//
// Created by PengFei_Zheng on 22/04/2017.
// Copyright © 2017 PengFei_Zheng. All rights reserved.
// #include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <queue>
#define MAX_SIZE 101
using namespace std; int s, n, m; struct N{
int a;
int b;
int c;
int t;
}; queue<N> myQueue;
bool visit[MAX_SIZE][MAX_SIZE][MAX_SIZE]; void x2y(int &x,int size_x, int &y,int size_y){
if(size_y - y >= x){
y+=x;
x = ;
}else{
x -=(size_y-y);
y = size_y;
}
} int BFS(int s, int n, int m){
while(!myQueue.empty()){
N nowP = myQueue.front();
myQueue.pop();
int a, b, c;
a = nowP.a;
b = nowP.b;
c = nowP.c;
x2y(a,s,b,n);// a--->b
if(visit[a][b][c]==false){
visit[a][b][c]=true;
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = nowP.t+;
if((a==s/ && b==s/) || (a==s/ &&c==s/) || (b==s/ && c==s/) ) return tmp.t;
myQueue.push(tmp);
}
a = nowP.a;
b = nowP.b;
c = nowP.c;
x2y(a,s,c,m);// a--->c
if(visit[a][b][c]==false){
visit[a][b][c]=true;
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = nowP.t+;
if((a==s/ && b==s/) || (a==s/ &&c==s/) || (b==s/ && c==s/) ) return tmp.t;
myQueue.push(tmp);
}
a = nowP.a;
b = nowP.b;
c = nowP.c;
x2y(b,n,a,s);// b--->a
if(visit[a][b][c]==false){
visit[a][b][c]=true;
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = nowP.t+;
if((a==s/ && b==s/) || (a==s/ &&c==s/) || (b==s/ && c==s/) ) return tmp.t;
myQueue.push(tmp);
}
a = nowP.a;
b = nowP.b;
c = nowP.c;
x2y(b,n,c,m);// b--->c
if(visit[a][b][c]==false){
visit[a][b][c]=true;
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = nowP.t+;
if((a==s/ && b==s/) || (a==s/ &&c==s/) || (b==s/ && c==s/) ) return tmp.t;
myQueue.push(tmp);
}
a = nowP.a;
b = nowP.b;
c = nowP.c;
x2y(c,m,a,s);// c--->a
if(visit[a][b][c]==false){
visit[a][b][c]=true;
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = nowP.t+;
if((a==s/ && b==s/) || (a==s/ &&c==s/) || (b==s/ && c==s/) ) return tmp.t;
myQueue.push(tmp);
}
a = nowP.a;
b = nowP.b;
c = nowP.c;
x2y(c,m,b,n);// c--->b
if(visit[a][b][c]==false){
visit[a][b][c]=true;
N tmp;
tmp.a = a;
tmp.b = b;
tmp.c = c;
tmp.t = nowP.t+;
if((a==s/ && b==s/) || (a==s/ &&c==s/) || (b==s/ && c==s/) ) return tmp.t;
myQueue.push(tmp);
}
}
return -;
} int main(){
while(scanf("%d%d%d",&s,&n,&m)!=EOF){
if(s==) break;
if(s%==){
printf("NO\n");
continue;
}
for(int i = ; i <= s ; i++){
for(int j = ; j <= n ; j++){
for(int k = ; k <= m ; k++){
visit[i][j][k]=false;
}
}
}
while(!myQueue.empty()) myQueue.pop(); N tmp;
tmp.a = s;
tmp.b = tmp.c = tmp.t = ;
myQueue.push(tmp);
visit[s][][]=true;
int ans = BFS(s,n,m);
ans == - ? printf("NO\n") : printf("%d\n",ans);
}
}
/**************************************************************
Problem: 1457
User: zpfbuaa
Language: C++
Result: Accepted
Time:10 ms
Memory:2528 kb
****************************************************************/