存档

文章标签 ‘DFS’

POJ 1562 Oil Deposits[DFS]

2011年9月3日 没有评论

题目大意:就是求油田的块数,如果一个小油田位于另一个小油田的周围的小矩形上(周围八个小方格),那么认为这两个油田是连通的,求有多少个这样的连通块。
解题思路:DFS搜索,两重循环遍历矩阵,如果这个节点是油田,就从这一个节点出发进行DFS,DFS过程中要进行标记,DFS返回后意味着发现一个连通块。我觉得BFS也是可以的 [em021]
传送门:POJ 1562 Oil Deposits http://poj.org/problem?id=1562
Problem: 1562 Memory: 18[......]

继续阅读

分类: POJ解题报告 标签:

POJ 1321 棋盘问题[DFS]

2011年9月2日 没有评论

题目描述:在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
深搜,某一行放不放子的问题,大概是这样。中间判断一下某一列可不可以放子就好了。DFS返回条件是没有子可放了或者行数超出限制了。题目的数据量也不算大,直接用朴素的DFS就可以解决了。

#include <iostream>
#include <cstdio>
#i[......]

继续阅读

USACO Mother’s Milk|DFS

2010年12月2日 2 条评论

USACO Mother's Milk以前在POJ上面看到过类似的题目,就是搜索所有可能的状态。对于每一个状态都可能存在6中转换:A->B, A->C; B->A, B->C; C->A, C->B,当然只能选择其中的一种。搜索其中的每一种状态即可。属于简单型的DFS。可以用一个20×20×20的数组来判重。

/*
ID:stackex1
LANG:C++
PROG:milk3
*/
#include <iostr[......]

继续阅读

分类: USACO题解 标签: ,