poj 1753 Flip Game(搜索:DFS+水题)

本文主要是介绍poj 1753 Flip Game(搜索:DFS+水题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

之前看了这个题感觉好难啊,再看看网上写的解题报告觉得整个人都不好了

结果尼玛直接深搜就可以了...

因为枚举2的16次方状态才65536种情况...

肯定不会超时

所以说以后看到DFS的题不要觉得有多复杂,一个步骤一个步骤遍历就行了

代码如下:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 5
using namespace std;int g[MAXN][MAXN];
int ans = 17;void deal(int x, int y) {if(x>=0 && x<4 && y>=0 && y<4)g[x][y] = !g[x][y];
}void turn(int pos) {int x = pos/4;int y = pos%4;deal(x, y);deal(x-1, y);deal(x+1, y);deal(x, y-1);deal(x, y+1);
}void dfs(int pos, int times) {if(pos == 16) {int tot = 0;for(int i=0; i<4; ++i) {for(int j=0; j<4; ++j) {tot += g[i][j];}}if(tot%16 == 0)ans = min(ans, times);return;}dfs(pos+1, times);//当前位置不翻转turn(pos);dfs(pos+1, times+1);//当前位置翻转turn(pos);//回到翻转钱的状态return ;
}int main(void) {char ch;for(int i=0; i<4; ++i) {for(int j=0; j<4; ++j) {(ch=getchar()) == 'b' ? g[i][j] = 1 : g[i][j] = 0;}getchar();}dfs(0, 0);if(ans == 17)cout << "Impossible" << endl;else cout << ans << endl;return 0;
}

这篇关于poj 1753 Flip Game(搜索:DFS+水题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---