poj 1753 Flip Game【dfs】

青旅半醒 2022-08-05 08:22 167阅读 0赞

Flip Game

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 34930</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 15289</td> 
  </tr> 
 </tbody> 
</table>

![1753_1.jpg][]

题目大意：给一个4x4的棋盘，棋盘上放置棋子，棋子一面白一面黑，现在给出一个棋局，让我们计算最少需要几步才能把所有棋都翻到黑面或者白面（翻棋子时，被翻棋子的上下左右的棋子也要翻）；

Sample Input

bwwb
    bbwb
    bwwb
    bwww

Sample Output

思路：笔者先想到的是用dfs；

因为棋盘是4x4的，所以数组开个6x6的足够了；然后把数组初始化为零；每个棋子只能翻奇数次或者不翻，而翻奇数次的与翻一次的效果一样，所以对于整个过程，最多只能翻16次，从只翻0次到翻15次遍历过去；

已Accept代码（c++提交）

#include <iostream>
    using namespace std;
    int p[6][6] = {0};	//棋盘 
    bool k;
    int s;				//累计最小需要翻的次数 
    int dr[] = {0, 0, 1, -1, 0};
    int dc[] = {1, -1, 0, 0, 0}; 
    
    bool all() {				//判断是否都为 白 或 黑 
    	for(int i = 1; i < 5; i++)
    		for(int j = 1; j < 5; j++)
    			if(p[i][j] != p[1][1])
    				return false;
    	return true;
    }
    
    void fq(int r, int c){		//翻转棋子 
    	for(int i = 0; i < 5; i++)
    		p[r + dr[i]][c + dc[i]] =! p[r + dr[i]][c + dc[i]];
    	return ;
    }
    
    void dfs(int r, int c, int d){
    	if(d == s){				//判断是否 都为 白 或 黑 
    		k = all();
    		return ;
    	}
    	if(k || r == 5) return ;
    	fq(r, c);				//翻转棋子 
    	if(c < 4)
    		dfs(r, c + 1, d + 1);
    	else
    		dfs(r + 1, 1, d + 1);
    	fq(r, c);				//恢复到上一步 
    	if(c < 4)
    		dfs(r, c + 1, d);
    	else
    		dfs(r + 1, 1, d);
    	return ;
    }
    
    int main() {
    	int i, j;
    	char t;
    	for(i = 1; i < 5; i++)
    		for(j = 1; j < 5; j++){
    			cin >> t; 
    			if(t == 'b')
    				p[i][j]= 1;		//用 0 与 1 代表白棋和黑棋 
    		}
    	for(s = 0; s < 16; s++){	//从翻转 0 个到翻转 15 个遍历过去 
    		dfs(1, 1, 0);
    		if(k) break;
    	}
    	if(k) cout << s << endl;
    	else 
    	cout << "Impossible" << endl;
    	return 0;
    }

还有bfs的做法和位运算的做法，明天补上：

[1753_1.jpg]: /images/20220731/0ff4a55405c3422b811f5a4a239e3167.png