递归和简单dfs 近期题目整理2.0 _递归

1.HDU-1207
题目描述：
经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩，当然这个传说并不可信，如今汉诺塔更多的是作为一个玩具存在。就收到了一个汉诺塔玩具作为生日礼物。
是个怕麻烦的人（恩，就是爱偷懒的人），很显然将64个圆盘逐一搬动直到所有的盘子都到达第三个柱子上很困难，所以决定作个小弊，他又找来了一根一模一样的柱子，通过这个柱子来更快的把所有的盘子移到第三个柱子上。下面的问题就是：当在一次游戏中使用了N个盘子时，他需要多少次移动才能把他们都移到第三个柱子上？很显然，在没有第四个柱子时，问题的解是2^N-1，但现在有了这个柱子的帮助，又该是多少呢？
AC代码：
#includeusing namespace std;#define LL long longLL f[70];int n;int main(){f[1] = 1;f[2] = 3;f[3] = 5;for(int i = 3;i <= 64;i++){LL minn = 0x3f3f3f3f3f3f;for(int j = 1;j < i;j++){if(2*f[j] + pow(2,i - j) - 1 < minn){minn = 2*f[j] + pow(2,i - j) - 1;}}f[i] = minn;}while(~scanf("%d",&n)){printf("%lld\n",f[n]);}return 0;}
这个题首先需要有一个知识铺垫：经典汉若塔问题里，移动的次数满足2^N-1次。这里的话给了四根柱子，所以再去推一个公式不太现实……
这里这样考虑：先把A柱子上的X个盘子移到第四个柱子D上，经过了f[X]次移动，接下来把剩下的盘子移动到柱子C上，这就是一个经典汉若塔问题了，然后把D上的盘子移动到C上就可以。
2.POJ-1979 Red And Black
题目描述：
【递归和简单dfs近期题目整理2.0】There is aroom,withtiles. Each tile isred or black. A man ison a black tile. From a tile, he can move to one of fourtiles. But he can’t move on red tiles, he can move only on black tiles.
Write ato count theof black tiles which he can reach bythe movesabove.
Input:
The inputofdata sets. A data setwith a linetwoW and H; W and H are theof tiles in the x- and y- , . W and H are not more than 20.
There are H more lines in the data set, each of whichW . Eachthe color of a tile as .
‘.’ - a black tile
‘#’ - a red tile
‘@’ - a man on a black tile(once in a data set)
The end of the input isby a lineof two zeros.
:
For each data set, youra line whichtheof tiles he can reach from thetile ( ).
AC代码：
#includeusing namespace std;const int maxn = 25;char a[maxn][maxn];int w,h,ans;void dfs(int x,int y){if(x - 1 >= 0&&a[x - 1][y] == '.'){a[x - 1][y] = '#';dfs(x - 1,y);ans++;}if(x + 1 < h&&a[x + 1][y] == '.'){a[x + 1][y] = '#';dfs(x + 1,y);ans++;}if(y - 1 >= 0&&a[x][y - 1] == '.'){a[x][y - 1] = '#';dfs(x,y - 1);ans++;}if(y + 1 < w&&a[x][y + 1] == '.'){a[x][y + 1] = '#';dfs(x,y + 1);ans++;}}int main(){int manx,many;while(cin >> w >>h){if(w == 0&&h == 0) return 0;ans = 0;for(int i = 0;i < h;i++){for(int j = 0;j < w;j++){cin >> a[i][j];if(a[i][j] == '@'){manx = i;many = j;}}}a[manx][many] = '#';ans++;dfs(manx,many);cout << ans << endl;}return 0;}
本题应该说是一个比较简单的DFS的题目，类似于走迷宫问题，@为当前的位置，#的位置是可以走的，所以直接锁定范围DFS即可。注意DFS的时候要分别考虑四个方向的情况。