首页 > 代码库 > POJ 1753 Flip Game
POJ 1753 Flip Game
http://poj.org/problem?id=1753
拿到这道题第一想法就是深搜。
简单介绍一下题意：
一个4*4棋盘， 输入为初始状态。flip一颗棋子， 本身和周围的四颗棋子会跟着翻动， 问最短需要翻动几颗棋子可以使棋盘全部黑或者白？
首先看一下从题中得到的信息：
1. 这个棋盘很小， 4*4
2. 翻动一个棋子两次相当于没翻， 于是步数最大只能为16
于是想到可以将深度作为函数的参数， 将从0依次递增的步数作为终止条件， 即当深度等于步数长度的时候就判断当前棋盘状态是否OK，如果不OK就继续回溯， 直至走完当前规定步数的所有情况。
#include <cstdio>#include <iostream>#include <algorithm>using namespace std;int map[5][5];int step;int flag;const int dx[5] = { 0, 0, 0, 1, -1 };const int dy[5] = { 0, 1, -1, 0, 0 };bool is_ok() { int sum = 0; for( int i = 0; i < 4; i++ ) { for( int j = 0; j < 4; j++ ) { sum += map[i][j]; } } if( sum == 0 || sum == 16 ) return true; else return false;}bool is_valid( int x, int y ) { if( 0 <= x && x <= 3 && 0 <= y && y <= 3 ) return true; else return false;}void flip( int x, int y ) { for( int i = 0; i <= 4; i++ ) { int x2 = x + dx[i]; int y2 = y + dy[i]; if( is_valid( x2, y2 ) ) { map[x2][y2] = !map[x2][y2]; } }}void dfs( int x, int y, int deep ) { if( deep == step ) { flag = is_ok(); return; } if( flag || x == 4 ) return; flip( x, y ); if( y < 3 ) dfs( x, y+1, deep+1 ); else dfs( x+1, 0, deep+1 ); flip( x, y ); if( y < 3 ) dfs( x, y+1, deep ); else dfs( x+1, 0, deep ); return;}int main() { char ch; for( int i = 0; i < 4; i++ ) { for( int j = 0; j < 4; j++ ) { cin >> ch; if( ch == ‘b‘ ) map[i][j] = 0; else map[i][j] = 1; } } for( step = 0; step <= 16; step++ ) { flag = false; dfs( 0, 0, 0 ); if( flag ) break; } if( flag ) { cout << step << endl; } else { cout << "Impossible" << endl; } return 0;}
这本来是道很简单的dfs题， 我却做了挺久， 究其原因， 还是太水。 引用邝神一句话：“人十我百， 人百我万！”
POJ 1753 Flip Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。