题目链接

费解的开关

题目大意

在一个5X5的矩阵中,点击任意一个位置,该位置及其上下左右四个相邻的位置中的数字都会变化(0变1,1变0),问能否在6步以内让01矩阵变成全1矩阵。

解题思路

1.每个位置最多点击一次。

2.点击的顺序不会影响最终的结果

3.固定第一行,当第i行的位置是0时,只能点击第i+1行的位置,改变第i行的位置只能通过改变第i+1行的位置来改变第i行的位置

第一行枚举可以用位运算的方式枚举

AC代码

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
char ch;
int a[10][10],t[10][10];
bool Check()  //全亮true,否则false
{
    rep(i,1,5)
        rep(j,1,5)
            if(!t[i][j]) return false;
    return true;
}
void Change(int x,int y)
{
    t[x][y]^=1;   //本身
    t[x-1][y]^=1;  //左
    t[x][y-1]^=1;  //上
    t[x+1][y]^=1;  //右
    t[x][y+1]^=1;  //下
}
void work()
{
    int ans=0x3f3f3f3f;
    rep(i,1,1<<5){  //枚举第一行所有状态,第i位是0不用按
        int tm=0;
        rep(j,1,5)
            rep(k,1,5)
                t[j][k]=a[j][k];
        rep(j,1,5)
            if(i>>(j-1)&1)  //C++里面从第0位开始,或者写成 i>>(j-1)&0==0
            {
                Change(1,j);
                tm++;
            }
        rep(j,1,4)  //控制第i+1行
            rep(k,1,5)
                if(!t[j][k])
                {
                    Change(j+1,k);
                    tm++;
                }
        if(Check()) ans=min(ans,tm);
    }
    if(ans>6) puts("-1");
    else printf("%d\n",ans);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        getchar();
        rep(i,1,5){
            rep(j,1,5){
                scanf("%c",&ch);
                a[i][j]=ch-48;
            }
            getchar();
        }
        work();
    }
    return 0;
}

题目链接

Strange Towers of Hanoi

题目大意

解出n个盘子4座塔的汉诺塔问题最少需要多少步?

解题思路

关于三座汉诺塔问题的最少步骤,有d[n]=2*d[n-1]+1。就是说把前n-1个盘子从A柱移动到B柱,然后把第n个盘子从A柱移动到C柱,最后把前n-1个盘子从B柱移动到C柱

dp[n]=min{[2*dp[i]+d[n-i]}(1<=i<=n)

dp[1]=1表示先把第i个盘子在四塔模式下移动到B柱,然后把n-i个盘子在3塔模式下移动到D柱,最后把i个盘子在四塔模式下移动到D柱,考虑所有可能的i取最小值

AC代码

#include <stdio.h>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
int dist[20],dp[20];
int main()
{
    dist[1]=1;
    rep(i,1,12) dist[i]=dist[i-1]*2+1;
    memset(dp,0x3f,sizeof dp);
    dp[1]=1;
    rep(i,2,12)
        rep(j,1,i-1)
            dp[i]=min(dp[i],dist[i-j]+2*dp[j]);
    rep(i,1,12) printf("%d\n",dp[i]);
    return 0;
}

一个爱折腾且喜欢研究算法的大学生