当前位置：首页 > news >正文

牛客小白月赛104-D小红开锁-模拟

news 2024/11/9 0:22:43

题目

小红来到了地下城的门口，发现门口有一个密码锁。
这个锁一共有n层，每层为一个正方形的图案。小红每次操作一次可以选择一层使其每个位置的元素按顺时针移动一个格子。
该图演示一个3层的锁，小红操作第二层时的变化。
在这里插入图片描述
该锁以中心为原点建立平面直角坐标系后，每个象限为一个区域，共分为4个区域，当且仅当某个区域内全部为’X’图案、且其余三个区域全部为’O’图案时，锁被解开。
小红想知道，这个锁需要操作最少多少次可以解开？
在这里插入图片描述

示例

2
OXXX
OOOO
OXOO
OOOO

输出

解题

题目就是模拟旋转比较麻烦，提供一个简单的思路，从最外圈开始转，转的时候判断如果碰到边界或者遇到被标记的点就不再走了，走过的标记，这样从外到内用这一个条件就可以做到“到头换向”，不需要再去算坐标了，换向用加一取模即可，把走过的地方放到vector数组中，然后用一个int变量去遍历，全是X和全是O走完到哪个位置，然后计算出需要转多少次。

#include <bits/stdc++.h>
using namespace std;
int main() {cin.tie(0)->sync_with_stdio(0), cout << fixed << setprecision(20);
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endifint t = 1;// #ifndef ONLINE_JUDGE// cin >> t;// #endifwhile (t--) {int n;cin >> n;vector<vector<int>> v(n * 2, vector<int>(n * 2));for (auto &row : v)for (auto &e : row) {char c;cin >> c;e = c == 'X';}vector<vector<bool>> vis(n * 2, vector<bool>(n * 2));static constexpr std::array<std::array<int, 2>, 4> dirs{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};int cost[4]{};for (int d = 0, cnt = (n * 2 - 1) * 4; d < n; d++, cnt -= 8) {vector<int> a;int i = d, j = n, k = 0;while (a.size() < cnt) {vis[i][j] = true;a.push_back(v[i][j]);int i2, j2;i2 = i + dirs[k][0];j2 = j + dirs[k][1];if (i2 < 0 or i2 >= n * 2 or j2 < 0 or j2 >= n * 2 or vis[i2][j2]) {k = (k + 1) % 4;i2 = i + dirs[k][0];j2 = j + dirs[k][1];}i = i2, j = j2;}int pos = 0;while (a[pos]) pos++;while (!a[pos]) pos = (pos + 1) % a.size();cost[0] += (0 + a.size() - pos) % a.size();cost[1] += (a.size() / 4 + a.size() - pos) % a.size();cost[2] += (a.size() / 2 + a.size() - pos) % a.size();cost[3] += (a.size() * 3 / 4 + a.size() - pos) % a.size();}cout << ranges::min(cost);}
}