Aizu - 0525 Osenbei (DFS)

冷不防 2022-03-10 04:10 93阅读 0赞

[https://cn.vjudge.net/problem/Aizu-0525][https_cn.vjudge.net_problem_Aizu-0525]

问题描述:

将题目中的烧饼抽象成01矩阵,可以一次使一行或者一列中的01反转,请问若干次翻转后1最多的情况?

解题思路:

一开始打算用两次DFS来模拟行列翻转,结果超时了,其实列翻转是不用模拟的,每列中有若干1和0,我们判断1的数量是否大于0,如果1的数量大于0,那么我们就保存1的数量(也就是不翻转),如果0的数量小于1,那么我们保存0的数量(翻转)

所以只需一次DFS即可

#include <iostream>
    #include <algorithm>
    using namespace std;
    bool hsTables[15][10010];
    int N, M;
    int bestRes = 0;
    void rowChange(int x) {
    	for (int i = 0; i < M; ++i) {
    		hsTables[x][i] = !hsTables[x][i];
    	}
    }
    //行深搜
    void DFS_Row(int x) {
    	if (x == N) {  
    		//每列有两种选择,翻转与不翻转。不需模拟,只需选择正面和背面数量最多的那一组即可
    		int ssum = 0;
    		for (int j = 0; j < M; ++j) {
    			int tempColunums = 0;
    			for (int i = 0; i < N; ++i) {
    				if (hsTables[i][j] == true) {
    					tempColunums++;
    				}
    			}
    			ssum += max(tempColunums, N - tempColunums);
    		}
    		bestRes = max(bestRes, ssum);
    		return;
    	}
    	DFS_Row(x + 1);	//不翻
    	rowChange(x);   
    	DFS_Row(x + 1); //
    }
    
    int main() {
    	while (true) {
    		cin >> N >> M;
    		int tempRes;
    		if(N == 0 && M == 0) break;
    		for (int i = 0; i < N; ++i) {
    			for (int j = 0; j < M; ++j) {
    				cin >> tempRes;
    				if (tempRes == 1) hsTables[i][j] = true;
    				else hsTables[i][j] = false;
    			}
    		}
            //开始递归搜索
    		bestRes = 0;
    		DFS_Row(0);
    		cout << bestRes << endl;
    	}
    
    	system("PAUSE");
    	return 0;
    }

[https_cn.vjudge.net_problem_Aizu-0525]: https://cn.vjudge.net/problem/Aizu-0525