每一行的灭灯0都可以由下一行对应位置进行打开~~
做法:
第一行的第一个位置可以操作,也可以不操作(0 - 1)
二进制枚举第一行的每一个位置的操作情况
确定第一行所有位置的操作情况,第二行对应得把第一行的灭灯打开,以此类推~~~
记录一下操作次数,不断更新最小操作次数即可
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 7;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
char g[N][N], temp[N][N];
int n, m;
bool judge_noleg(int x, int y){
return x < 0 || y < 0 || x > 5 || y > 5;
}
void tran(int x, int y){
if(judge_noleg(x, y))return;
g[x][y] ^= 1;
for(int i = 0;i < 4;i ++){
int nx = x + dx[i];
int ny = y + dy[i];
if(judge_noleg(nx, ny))continue;
g[nx][ny] ^= 1;
}
}
int work(){
int res = 0x3f3f3f3f;
memcpy(temp, g, sizeof(g));
for(int i = 0;i < (1 << 5);i ++){
int ans = 0;
for(int j = 0;j < 5;j ++)
if((i >> j) & 1){
tran(0, j);
ans ++;
}
for(int e = 0;e < 4;e ++)
for(int f = 0;f < 5;f ++)
if(g[e][f] == '0'){
tran(e + 1, f);
ans ++;
}
bool flag = 1;
for(int f = 0;f < 5;f ++){
if(g[4][f] == '0'){
flag = 0;
break;
}
}
if(flag)
res = min(res, ans);
memcpy(g, temp, sizeof(g));
}
if(res > 6)return -1;
return res;
}
int main(){
scanf("%d", &n);
while(n --){
for(int i = 0;i < 5;i ++)
scanf("%s", g[i]);
printf("%d\n", work());
}
return 0;
}
大佬,可以帮我看看这个哪里写错了吗?三个答案都是-1
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
const int INF = 100000;
char g[10][10];
int dx[4] = {-1 , 0 , 1, 0};
int dy[4] = {0 , 1 , 0 ,-1};
void turn(int x , int y)
{
for(int i = 0;i < 4;i)
{
int ax = x + dx[i];
int ay = y + dy[i];
if(ax >= 0 && ax < 5 && ay >= 0 && ay < 5)
{
g[ax][ay] ^= 1;
}
}
}
int word()
{
int ans = INF;
for(int k = 0;k < 1 << 5;k)
{
char backup[10][10];
memcpy(backup , g , sizeof(g));
int res = 0;
for(int j = 0;j < 5;j)
{
if(k >> j & 1)
{
res;
turn(0,j);
}
}
for(int i = 0;i < 4;i)
{
for(int j = 0;j < 5;j)
{
if(g[i][j] == ‘0’)
{
res;
turn(i + 1 , j);
}
}
}
bool is_successful = true;
for(int j = 0;j < 5;j)
{
if(g[4][j] == ‘0’)
{
is_successful = false;
break;
}
}
if(is_successful) ans = min(ans , res);
memcpy(g , backup , sizeof(g));
}
if(ans > 6) return -1;
return ans;
}
int main()
{
int T;
cin >> T;
while(T–)
{
for(int i = 0;i < 5;i++)
{
cin >> g[i];
}
cout << word() << endl;
}
return 0;
}