数据结构--黑白棋

时间：2025-04-07 21:44:38
  • // 黑白棋.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
  • //给定?个棋盘，N?，M列，其中3=<M<=20，3=<N<=100，该棋盘被 ??和??的棋?填满，如果某
  • //??都是?棋，我们称这??为?条 路，假设棋盘可以按列翻转（该列棋?颜?取反），给定?个K
  • //值，3 = < K <= M, 对棋盘翻转K次（必须翻转K次，可以选择翻转任?列，也可以 对某?列多次翻转）求解
  • //经过K次翻转以后，最多有?条路？，如果没有?条路，输出 - 1
  • #include <iostream>
  • using namespace std;
  • int N, M, k, minn = 0, q = 0;
  • int board[101][21], boardCopy[101][21];
  • int col[101], book[101];
  • int path[21];
  • //计算有多少路
  • int road(int path[21]) {
  • //行数
  • int co=N ;
  • //复制
  • for (int i = 1;i <= N;i++)
  • for (int j = 1;j <= M;j++)
  • boardCopy[i][j] = board[i][j];
  • //翻转
  • for (int i = 1;i <= N;i++)
  • for (int j = 1;j <= k;j++) {
  • if (boardCopy[i][path[j]] == 0)
  • boardCopy[i][path[j]] = 1;
  • else
  • boardCopy[i][path[j]] = 0;
  • }
  • //找路
  • for (int i = 1;i <= N;i++)
  • for (int j = 1;j <= M;j++) {
  • if (boardCopy[i][j] == 0) {
  • co=co-1;
  • break;
  • }
  • }
  • return co;
  • }
  • void init() {
  • for (int i = 1;i <= M;i++)
  • col[i] = i;
  • }
  • void dfs(int nowk, int step) {
  • int nextk;
  • //如果已经翻转了k次，那么判断当前有多少条路，找出最多的
  • if (step == k) {
  • int maxroad = road(path);
  • if (maxroad > minn){
  • minn = maxroad;
  • //cout << minn;
  • }
  • return;
  • }
  • for (int i = nowk;i <= M;i++) {
  • path[step + 1] = i;
  • dfs(i, step + 1);
  • }
  • return;
  • }
  • int main()
  • {
  • int T;
  • cin >> T;
  • for (int i = 1;i <= T;i++) {
  • cin >> N >> M >> k;
  • for (int p = 1;p <= N;p++)
  • for (int q = 1;q <= M;q++)
  • cin >> board[p][q];
  • init();
  • for (int i = 1;i <= M;i++) {
  • path[1] = i;
  • dfs(i, 1);
  • }
  • cout<<minn<<endl;
  • minn = 0;
  • }
  • return 0;
  • }
  • /*
  • 1
  • 4 4 3
  • 1 0 1 1
  • 1 1 0 1
  • 0 1 1 1
  • 1 1 0 1
  • 7
  • 9 8 3
  • 0 0 0 0 0 0 0 0
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 9 8 4
  • 0 0 0 0 0 0 0 0
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 9 8 5
  • 0 0 0 0 0 0 0 0
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 9 8 6
  • 0 0 0 0 0 0 0 0
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 12 8 3
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 0 0 0 0 0 0 0 0
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 12 8 4
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 0 0 0 0 0 0 0 0
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 12 8 5
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 0 0 0 0 0 0 0 0
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 1 1 0 0 0 0 0
  • 1 1 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • 1 0 1 1 1 1 1 1
  • */

    • 相关文章