忠告POUR1上SPOJ？ [英] Advice for POUR1 on SPOJ?
问题描述
我需要这个问题 POUR1 帮助。我觉得 它可以与暴力破解的方法来解决，但我读，这是一个问题图表（BFS）。我解决了像ABCPATH，LABYR1，PT07Y，PT07Z，位图...问题_ 但我不知道如何处理POUR1在BFS的方式。
有人可以给我一些建议吗？
问题陈述：
给定两个容器，其中一个可容纳一升的水和其他 - B升水，确定的，以获得精确地的c水升在一个容器中所需的步骤数
在开始两艘船都是空的。下面的操作被算作'步骤'：
- 排空容器，
- 填充的容器，
- 浇的水从一个容器到另一个，不会溢出，直到一个容器中已满或为空。
输入：
这是整数t，1所述; = T＆其中; = 100，表示测试用例的数量，随后的输入数据的叔组，每组由三个正整数a，B，C，不超过40000时，在不同的行定
输出：
有关各组输入数据，输出的最小数目以获得缺失了C升所需的步骤，或者为-1，如果这是不可能的。
示例：
样品输入：
2
五
2
3
2
3
4
示例输出：
2
-1
考虑集合所有的的先验的候选条件的状态（例如[3,7]意Vessel1包含3升和vessel2包含7个窝）。你有向图的顶点是那些国家，其边缘是可能的行动。的问题是要找到[0 0]，类型的任一状态并[c，？]或的类型[？，C]的状态下在图中的路径连接的状态。这样的路径通常搜查一个BFS。
I need help with this problem POUR1. I think
it can be solved with bruteforce approach, but I read that it is a graph problem (BFS). I solved problems like ABCPATH, LABYR1, PT07Y, PT07Z, BITMAP, ...
But I don't know how to approach POUR1 in BFS manner.
Can someone give me some advice?
Problem statement:
Given two vessels, one of which can accommodate a litres of water and the other - b litres of water, determine the number of steps required to obtain exactly c litres of water in one of the vessels.
At the beginning both vessels are empty. The following operations are counted as 'steps':
- emptying a vessel,
- filling a vessel,
- pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.
Input:
An integer t, 1<=t<=100, denoting the number of testcases, followed by t sets of input data, each consisting of three positive integers a, b, c, not larger than 40000, given in separate lines.
Output:
For each set of input data, output the minimum number of steps required to obtain c litres, or -1 if this is impossible.
Example:
Sample input:
2
5
2
3
2
3
4
Sample output:
2
-1
Consider the set of all a priori possibles states (eg [3, 7] meaning Vessel1 contains 3 litters and vessel2 contains 7 litters). You have a directed graph whose vertices are those states and whose edges are the possible moves. The question is to find a path in the graph joining the state [0, 0] to either a state of type [c, ?] or a state of type [?, c]. Such a path is typically searched by a BFS.
这篇关于忠告POUR1上SPOJ？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
