Fliptile
解题思路
- 对于这个题目可以用递推来写
- 因为每次翻转只会影响一个十字架的区域,所以如果我们知道第一行的情况,那么是不是只要把第一行的所有的1在对应的下一个行的相同位置进行翻转就可以把第一行的所有的1变成0呢(重要性质)
- 那么只要我们不断递推下去就可以得到最后一行的状态,如果最后一行全是0,代表方案合法
- 那么我们怎么得到第一行的状态呢?
- 很明显第一行的状态是固定的,只有2 ^ m列种情况
- 那么我们只要枚举这2 ^ m列种情况就可以得到我们的答案
- 注意因为第一行的状态可以由第一行的原始状态,通过翻转操作得到第一行所有状态(注意枚举的是翻转操作,不是第一行的状态)
- 所有我们只要枚举翻转的操作就可以了,同时题目也说叫我们打印翻转的次数
代码实现
#include <iostream>
#include <cstring>
using namespace std;
const int N = 16;//矩阵最大规模
const int INF = 100000;//表示一个无穷大的数
int n;//矩阵的行数
int m;//矩阵的列数
int martix[N][N];//原始矩阵
int backup[N][N];//暂时存放原始矩阵,用来恢复现场
int ans[N][N];//最终的答案,即翻转操作
int t[N][N];//每一次合法的答案
int d[5][2] = {
{1, 0}, {-1, 0}, {0, 0}, {0, -1}, {0, 1}
};
int res = INF;//操作的次数初始化为一个极大值
void filp(int x, int y)//翻转x,y位置的值
{
for (int i = 0; i < 5; i++) {
int nx = x + d[i][0];
int ny = y + d[i][1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
martix[nx][ny] ^= 1;
}
}
}
void solve()
{
//读入矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> martix[i][j];
backup[i][j] = martix[i][j];
}
}
//枚举所有的操作
for (int i = 0; i < 1 << m; i++) {
memset(t, 0, sizeof(t));//给t数组全部赋值为0
memcpy(martix, backup, sizeof(backup));//把backup数组的内容复制到martix数组
int cnt = 0;//统计翻转操作的次数
//看第一行有那些位置需要翻转
for (int j = 0; j < m; j++) {
if (i >> j & 1) {
filp(0, j);//翻转第一行的j位置
cnt++;//翻转了一次计数器加一
t[0][j] = 1;//计入翻转的位置
}
}
//只看到第n - 1行,因为最后一行没有灯了,所以推到n - 1行就可以了
for (int j = 0; j < n - 1; j++) {
for (int k = 0; k < m; k++) {
if (martix[j][k]) {//如果当前行的k位置是1,那么我们要把它变成0,那么就翻转它的下一行的位置
filp(j + 1, k);//翻转下一行来改变当前位置
t[j + 1][k] = 1;//翻转的是下一行所以记录j + 1位置
cnt++;//翻转了一次计数器加一
}
}
}
bool islaw = 1;//判断方案是不是能够让矩阵全为0,1代表合法即最后矩阵全为0,0代表不合法,矩阵没有全为0
//遍历最后一行
for (int j = 0; j < m; j++) {
if (martix[n - 1][j]) {//如果有一个1
islaw = 0;//方案不合法
break;//跳出循环
}
}
if (islaw) {//方案合法
if (cnt < res) {//并且比之前的答案的操作次数还要更少
res = cnt;//更新最少的操作次数
memcpy(ans, t, sizeof(t));//把新的答案复制到ans数组里面去
}
}
}
if (res != INF) {//如果res的值不是INF那么代表有合法的方案
//打印翻转操作数组
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << ans[i][j] << ' ';
}
cout << '\n';
}
}
else {//res == INF没有合法的方案,打印不可能
cout << "IMPOSSIBLE";
}
}
int main()
{
cin >> n >> m;//读入矩阵的行和列
solve();
return 0;
}
Shuffle'm Up
解题思路
- 一道模拟题,根据样例我们可以看出,它是每次分半组合,然后一直循环下去,但如果再次碰到第一次组合的结果,就代表无法得到想要的结果
代码解析
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 101
int t;
int main(int argc, char* argv[])
{
sc("%d", &t);
for (int i = 1; i <= t; i++) {
int c;
char s1[N] = { 0 };
char s2[N] = { 0 };
char s3[2 * N] = { 0 };
char s4[2 * N] = { 0 };//³õʼ״̬
char s5[2 * N] = { 0 };
bool is = 0;
sc("%d%s%s%s", &c, s1, s2, s3);
for (int i = 0; i < c; i++) {
s4[2 * i] = s2[i];
s4[2 * i + 1] = s1[i];
}
for (int i = 0; i < 2 * c; i++) {
s5[i] = s4[i];
}
int ans = 1;
while (1) {
for (int i = 0; i < c; i++) {
s1[i] = s4[i];
s2[i] = s4[i + c];
}
for (int i = 0; i < c; i++) {
s4[2 * i] = s2[i];
s4[2 * i + 1] = s1[i];
}
ans++;
if (strcmp(s4, s3) == 0) {
break;
}
if (strcmp(s4, s5) == 0) {
is = 1;
break;
}
}
if (is) {
pr("%d %d\n", i, -1);
}
else {
pr("%d %d\n", i, ans);
}
}
return 0;
}
标签:第一行,22,int,题解,矩阵,2024,++,include,翻转 From: https://www.cnblogs.com/lwj1239/p/18088955