POJ 1980

开始规划思路，一开始想错了，直接想着用BFS解决，对于这两者的理解也因为这更深刻了些。

BFS寻求源点到目的地的最短距离，而DFS才适合于这种树全搜索情况（当然更符合DFS的应用应该是算法导论上的拓扑排序以及相关连通分量）

这道题思路很简单，但是调试过程太曲折了，期间很多细节都没有重视，比如在搜索的中间过程并不需要重视约分化简的过程，但是等到叶子节点进行比较，即递归式的边界处的时候，这时候考虑周到的能力还需要更进一步的锻炼。

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <set>
using namespace std;

int DFS(int p, int q, int b, int a, int n)
{
	if (0== p){
		return 1;
	}
	if (1== n){
		if (0== q%p){
			q= q/p;
			p= 1;
		}
		if (1== p && q>= b && q<= a){
			return 1;
		}
		else{
			return 0;
		}
	}
	int ans= 0;

	for (int i= b, pp= p*b-q; i<= a; ++i, pp+= p){
		if (pp< 0){
			continue;
		}
		ans+= DFS(pp, q*i, i, a/i, n-1);
	}
	return ans;
}
int main()
{
	int p, q, a, n;
	while (~scanf("%d %d %d %d", &p, &q, &a, &n) && p){
		printf("%d
", DFS(p, q, 1, a, n));
	}

	return 0;
}