题解 | #小红的扫雷游戏#

小红的扫雷游戏

https://www.nowcoder.com/practice/e610b4dac2c747a09b926053df59c958

分析

非常好的模拟 + 位运算题目

因为棋盘最大是, 如果用二进制表示状态的话最多种状态

因此用二进制表示每个位置是否是雷, 对于初始状态已经有数字的部分自然不是雷

答案应该是初始状态的子集并且每个位置的数字和周围雷的排布情况应该是一样的

因此可以写一个函数判断当前状态是否是合法的, 具体实现看代码

实现代码

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 5, MOD = 998244353;
const LL INF = 1e18;

const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n = 4;
char g[N][N];

bool check(int s) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            char c = g[i][j];
            if (c == '.') continue;
            int cnt = 0;
            for (int k = 0; k < 8; ++k) {
                int nx = i + dx[k], ny = j + dy[k];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                int t = nx * 4 + ny;
                if (s >> t & 1) cnt++;
            }
            if (cnt != g[i][j] - '0') return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int s = (1 << 16) - 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
            if (g[i][j] != '.') s -= 1 << (i * 4 + j);
        }
    }

    int st[N][N] = {0};
    for (int i = 0; i < 1 << 16; ++i) {
        if ((i | s) == s && check(i)) {
            for (int r = 0; r < n; ++r) {
                for (int c = 0; c < n; ++c) {
                    int t = r * 4 + c;
                    if ((i & 1 << t) == 0) st[r][c] |= 1;
                    else st[r][c] |= 2;
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (st[i][j] == 1) {
                if (g[i][j] == '.') g[i][j] = 'O';
            }
            else if (st[i][j] == 2) g[i][j] = 'X';
            else g[i][j] = '.';
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << g[i][j];
        }
        cout << '\n';
    }

    return 0;
}
全部评论

相关推荐

1.自我介绍2.介绍一下mcp,&nbsp;skills3.了解react哪些状态管理库4.对话是sse还是什么?是用fetch还是EventSource?5.ts中的any&nbsp;和&nbsp;unknown讲一讲6.是直接用组件库的组件还是自己封装了一些别的7.代码输出题1function&nbsp;main()&nbsp;{{var&nbsp;a&nbsp;=&nbsp;1let&nbsp;b&nbsp;=&nbsp;2}console.log(a);console.log(b);}main()console.log(a);8.什么是块级作用域&nbsp;全局作用域&nbsp;函数作用域9.代码输出题2for&nbsp;(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(i);},&nbsp;100);}10.代码输出题3for&nbsp;(var&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&amp;lt;&nbsp;5;&nbsp;i++){function&nbsp;printText(temp)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(temp);},&nbsp;100);}printText(i)}11.代码输出题4for(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++){function&nbsp;printText(temp)&nbsp;{var&nbsp;temp&nbsp;=&nbsp;isetTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(temp);},&nbsp;100);}printText(i)}12.代码输出题5for(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++){function&nbsp;printText(temp)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{var&nbsp;temp&nbsp;=&nbsp;iconsole.log(temp);},&nbsp;100);}printText(i)}13.点击控制台输出题export&nbsp;default&nbsp;function&nbsp;App()&nbsp;{const&nbsp;[count,&nbsp;setCount]&nbsp;=&nbsp;useState(0)console.log('render',count)return&nbsp;(&lt;div&gt;&lt;h1&gt;{count}&lt;/h1&gt;{setCount(count&nbsp;+&nbsp;1)setTimeout(()&nbsp;=&amp;gt;&nbsp;console.log('setTimeout',&nbsp;count),&nbsp;1000)}}&amp;gt;+1&lt;/div&gt;)}//这个组件点击按钮后,控制台的输出顺序和值如下://&nbsp;1.&nbsp;render&nbsp;1&nbsp;(组件重新渲染,&nbsp;count&nbsp;更新为&nbsp;1)//&nbsp;2.&nbsp;setTimeout&nbsp;0&nbsp;(1秒后输出,注意这里是&nbsp;0&nbsp;而不是&nbsp;1)14.算法:给有序数组arr&nbsp;=&nbsp;[-4,&nbsp;-1,&nbsp;0,&nbsp;3,&nbsp;5],返回平方后的排序//&nbsp;有序数组平方后排序const&nbsp;arr&nbsp;=&nbsp;[-4,&nbsp;-1,&nbsp;0,&nbsp;3,&nbsp;5]function&nbsp;solution(arr)&nbsp;{const&nbsp;len&nbsp;=&nbsp;arr.lengthconst&nbsp;result&nbsp;=&nbsp;new&nbsp;Array(len)let&nbsp;left&nbsp;=&nbsp;0let&nbsp;right&nbsp;=&nbsp;len&nbsp;-&nbsp;1let&nbsp;index&nbsp;=&nbsp;len&nbsp;-&nbsp;1while&nbsp;(left&nbsp;&amp;lt;=&nbsp;right)&nbsp;{if&nbsp;(arr[left]&nbsp;*&nbsp;arr[left]&nbsp;&amp;gt;&nbsp;arr[right]&nbsp;*&nbsp;arr[right])&nbsp;{result[index]&nbsp;=&nbsp;arr[left]&nbsp;*&nbsp;arr[left]left++}&nbsp;else&nbsp;{result[index]&nbsp;=&nbsp;arr[right]&nbsp;*&nbsp;arr[right]right--}index--}return&nbsp;result}console.log(solution(arr));15.反问
查看14道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务