Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

好复杂啊、想了好久~~贴码留念下......

Posted by Ashly at 2016-08-09 17:57:19 on Problem 3414 and last updated at 2016-08-12 15:29:45
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>

typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MAXN = 100;
int MaxA, MaxB, C;//Pots A的最大容量;Pots B的最大容量;目标容量 C;
const string OPERA[] = {"-1", "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};//分别代表六种可能的操作
int visit[MAXN + 7][MAXN + 7];//visit[i][j] = 1表示Pots A的水量为 i, Pots B的水量为 j这一状态已经出现过.

struct Status {
	int NowA;//此时A中的水量
	int NowB;//此时B中的水量
	int step;//到达此状态的操作次数
	string order;//到达此状态的所有操作
};

Status BFS() {
	memset(visit, 0, sizeof(visit));
	Status fist;//初始状态
	fist.NowA = fist.NowB = fist.step = 0;
	fist.order = "";
	queue<Status> Qu;
	Qu.push(fist);//从初始状态开始BFS
	visit[0][0] = 1;
	while(!Qu.empty()) {
		Status temp = Qu.front();
		Qu.pop();
		if(temp.NowA == C || temp.NowB == C) return temp;//找到目标状态

		Status nex;
		
		if(temp.NowA != MaxA) {//A中水不为满,可执行操作1 --> FILL(1)
			nex.NowA = MaxA, nex.NowB = temp.NowB, nex.step = temp.step + 1;//执行操作1之后,状态发生变化,记录即可
			if(nex.step == 1) nex.order = temp.order + OPERA[1];
			else nex.order = temp.order + "\n" + OPERA[1];
			if(!visit[nex.NowA][nex.NowB]) {//这个状态没有发生过
				Qu.push(nex);
				visit[nex.NowA][nex.NowB] = 1;
			}
		}

		if(temp.NowB != MaxB) {//B中水不为满,可执行操作2 --> FILL(2)
			nex.NowA = temp.NowA, nex.NowB = MaxB, nex.step = temp.step + 1;
			if(nex.step == 1) nex.order = temp.order + OPERA[2];
			else nex.order = temp.order + "\n" + OPERA[2];
			if(!visit[nex.NowA][nex.NowB]) {
				Qu.push(nex);
				visit[nex.NowA][nex.NowB] = 1;
			}
		}

		if(temp.NowA != 0) {//A中水不为空,可执行操作3 --> DROP(1)
			nex.NowA = 0, nex.NowB = temp.NowB, nex.step = temp.step + 1;
			if(nex.step == 1) nex.order = temp.order + OPERA[3];
			else nex.order = temp.order + "\n" + OPERA[3];
			if(!visit[nex.NowA][nex.NowB]) {
				Qu.push(nex);
				visit[nex.NowA][nex.NowB] = 1;
			}
		}

		if(temp.NowB != 0) {//B中水不为空,可执行操作4 --> DROP(2)
			nex.NowA = temp.NowA, nex.NowB = 0, nex.step = temp.step + 1;
			if(nex.step == 1) nex.order = temp.order + OPERA[4];
			else nex.order = temp.order + "\n" + OPERA[4];
			if(!visit[nex.NowA][nex.NowB]) {
				Qu.push(nex);
				visit[nex.NowA][nex.NowB] = 1;
			}
		}
		
		if(temp.NowA != 0 && temp.NowB != MaxB) {//A中水不为空,且B中水不为满,可执行操作5 --> POUR(1,2)
			nex.NowA = max(0, temp.NowA - (MaxB - temp.NowB)), nex.NowB = min(MaxB, temp.NowA + temp.NowB);
			nex.step = temp.step + 1;
			if(nex.step == 1) nex.order = temp.order + OPERA[5];
			else nex.order = temp.order + "\n" + OPERA[5];
			if(!visit[nex.NowA][nex.NowB]) {
				Qu.push(nex);
				visit[nex.NowA][nex.NowB] = 1;
			}
		}

		if(temp.NowB != 0 && temp.NowA != MaxA) {//B中水不为空,且A中水不为满,可执行操作6 --> POUR(2,1)
			nex.NowA = min(MaxA, temp.NowA + temp.NowB), nex.NowB = max(0, temp.NowB - (MaxA - temp.NowA));
			nex.step = temp.step + 1;
			if(nex.step == 1) nex.order = temp.order + OPERA[6];
			else nex.order = temp.order + "\n" + OPERA[6];
			if(!visit[nex.NowA][nex.NowB]) {
				Qu.push(nex);
				visit[nex.NowA][nex.NowB] = 1;
			}
		}
	}
	return fist;//没找到答案
}

int main() {
        ios_base::sync_with_stdio(false);
	cin >> MaxA >>  MaxB >> C;
	Status ans = BFS();
	if(ans.NowA == C || ans.NowB == C) cout << ans.step << endl << ans.order << endl;
	else cout << "impossible" << endl;
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator