费解的开关
今天一天也没写出这题。。。
一开始是想着状态压缩第一行
然后发现没那么简单。。。
明天一定补题
应该要做一个timetable
不然感觉学的乱七八糟的
今天发现就是状态压缩
只是change的方式要变化下一行
费解的开关 说多了都是泪
还以为输出方法数 没想到是输出最小步数
注意是如果步数大于6的就输出-1
总体思路还是状态压缩
枚举第一行 然后先转换第一行枚举的结果
接着从第一行开始 遇到0的点就在其下方做一次改变，注意是其下方 因为如果是那个搜到的点变化的话，就会影响上面的点，而我们已经无法回去检测上面的点了 同时要注意枚举时行数是1~4，不需要枚举第五行了
#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x+'0'); } #define N 10 ll T; char ma[N][N],backup[N][N]; int ans[N][N],ress=1e9; int dx[]={0,0,-1,1,0},dy[]={1,-1,0,0,0}; void print(){ cout<<"p:"<<endl; for(int i=0;i<5;i++){ // for(int j=0;j<5;j++){ cout<<ma[i]<<endl; } cout<<endl; } void change(int x,int y){ for(int i=0;i<5;i++){ int tx=x+dx[i],ty=y+dy[i]; if(tx>=0&&tx<=4&&ty>=0&&ty<=4){ if(ma[tx][ty]=='1')ma[tx][ty]='0'; else ma[tx][ty]='1'; } } } void fun(){ for(int i=0;i<5;i++){ if(ans[0][i]){ change(0,i); } // cout<<ans[0][i]; } // cout<<endl; // print(); for(int i=0;i<4;i++){ for(int j=0;j<5;j++){ if(ma[i][j]=='0'){ change(i+1,j); ans[i+1][j]=1; } } } } bool check(){ int res=0; for(int i=0;i<5;i++){ for(int j=0;j<5;j++){ if(ans[i][j]){ res++; } if(ma[i][j]=='0')return 0; } } // if(res<=6)return 1; ress=min(ress,res); return 1; } void solve(){ ress=1e9; int answ=0; for(int i=0;i<5;i++)cin>>ma[i]; memcpy(backup,ma,sizeof(backup)); for(int i=0;i<(1<<5);i++){ for(int j=0;j<5;j++){ if((i>>j)&1){ ans[0][j]=1; }else { ans[0][j]=0; } } fun(); if(check()){ answ++; } memcpy(ma,backup,sizeof(ma)); memset(ans,0,sizeof(ans)); } if(ress<=6) cout<<ress<<endl; else cout<<"-1"<<endl; } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); //T=1; cin>>T; while(T--){ solve(); } return 0; }