下棋_牛客博客

题目

小L和小M在下棋。这张棋盘是 n×m 的。每一个格子要么是黑色的，要么是白色的。两个人轮流进行操作。小L先手。
每一次可以选择一个黑色的格子，以这个格子为右下角，棋盘左上角为左上角，构成一个矩阵，将这个矩阵的所有黑色变成白色，所有白色格子变成黑色。如果找不到一个黑色的格子，那么那个人就输了。
请问谁能赢呢。

解题思路

推测：每一次操作无论先选中哪个黑色格子，都不影响最终结果。
那么，每一次操作都选择接近棋盘右下角的那个黑色格子。这样，这个格子变成白色后不再会变成黑色。
如果每次操作，都对 board 进行颜色转换，那么时间复杂度会是 $O((nm)^2)$ 。
因此，另使用 change[i][j] 计算 board[i][j] 进行颜色变化的次数。
如果 change[i][j] 是偶数，表示当前 board[i][j] 颜色不变；否则当前颜色改变。
而 change[i][j] = change[i+1][j] + k，其中 k 表示第 i 行中，第 j 列之后的操作次数。
如果最后的操作总次数为奇数，则小L赢，否则小M赢。

C++代码

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int T;
    cin >> T;
    int n, m;
    while(T--){
        cin >> n >> m;
        vector<vector<char>> board(n, vector<char>(m));
        for(int i=0; i<n; ++i)
            for(int j=0; j<m; ++j)
                cin >> board[i][j];

        vector<vector<int>> change(n+1, vector<int>(m+1, 0));
        int cnt = 0;
        for(int i=n-1; i>=0; --i){
            int k = 0;
            for(int j=m-1; j>=0; --j){
                change[i][j] = change[i+1][j] + k;
                if(board[i][j]=='B' && change[i][j]%2==0){
                    cnt += 1;
                    k += 1;
                    change[i][j] += 1;
                }
                else if(board[i][j]=='W' && change[i][j]%2==1){
                    cnt += 1;
                    k += 1;
                    change[i][j] += 1;
                }
            }
        }
        if(cnt%2)
            cout << "L" << endl;
        else
            cout << "M" << endl;
    }
    return 0;
}

解题思路2

推测：每一次操作无论先选中哪个黑色格子，都不影响最终结果。

如果棋盘左上角的格子是黑色的，即 board[0][0]=='B'，那么，
①小L选中左上角的格子，格子变成白色，此时，
②要么，棋盘全部是白色，小M无法操作；
③要么，小M选中一个非左上角的黑色格子，左上角的格子变成黑色，此时，小L进行①操作。
如此循环，终止状态为②，小L赢。

如果棋盘左上角的格子是白色的，操作类似，小M赢。

C++代码

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int T;
    cin >> T;
    int n, m;
    while(T--){
        cin >> n >> m;
        vector<vector<char>> board(n, vector<char>(m));
        for(int i=0; i<n; ++i)
            for(int j=0; j<m; ++j)
                cin >> board[i][j];

        if(n>0 && m>0 && board[0][0]=='B')
            cout << "L" << endl;
        else
            cout << "M" << endl;
    }
    return 0;
}