题面
今天学搜索，正好水一发以前做的这道毒瘤题
话说这道题做了我一天，别人都是各种优化，不超100行
天真的我硬核刚了220行，全程0优化水过
但其实不用这么长，我有的函数写的有点重复了（
思路：
显然是dfs，一行一行的来
搜到[i, j]时(i > 1)，看[i - 1, j]是否为黑，是的话就翻转[i, j],
也就是说搜完当前行就要保证上一行的棋全都翻成了白色
当搜到最后一行时，
既要保证上一行翻成白色，还要保证自己也都翻成白色，
最后还要特判一下最后两个的翻转.
当时年少轻狂，我想着层次一定要清晰，
于是就SB地分别打了四个函数：
- 特判第一行,firstLineS
- 当只有一列的时候,dfs1
- 当搜到最后一行时或本来只有一行时，dfsn
- 正常搜索,dfs
这个题有个坑，92分卡了一下午: 搜到的第一个解不能直接输出，它是最优解，但不一定是字典序最小的，所以继续搜完
[collapse title="Code" status="false"]
#include <bits/stdc++.h>
using namespace std;
int n, m, a, minans = 99999;
int Chess[25][25], ans[25][25], minan[25][25];
void c(int i, int j)
{
if(Chess[i][j]%2 == 0) Chess[i][j] = 1;
else Chess[i][j] = 0;
}
void print()
{
a = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (Chess[i][j] % 2 == 1) return ;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
a += ans[i][j] % 2;
if(minans > a)
{
minans = a;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
minan[i][j] = ans[i][j] % 2;
}
}
int back1(int p)
{
if ( Chess[m][p] == 1 && p == n)
return 1;
else if (p != n)
return 1;
return 0;
}
int back2(int p)
{
if ( Chess[m][p] == 0 && p == n)
return 0;
else if (p != n)
return 0;
return 1;
}
void dfsn(int num) {
if (num == n + 1) {
print();
return ;
}
int line = m;
if (m == 1)
{
if (num == 1)
{
dfsn(num + 1);
c(line, num + 1);
c(line, num);
ans[line][num]++;
dfsn(num + 1);
}
if (Chess[line][num - 1]==0 && back2(num)==0)
dfsn(num+1);
else if (Chess[line][num - 1]==1 && back1(num)==1)
{
c(line, num - 1);
c(line, num + 1);
c(line, num);
ans[line][num]++;
dfsn(num + 1);
}
}
else if (num == 1)
{
if (Chess[m - 1][1] == 0)
dfsn(2);
else
{
c(m - 1 , 1);
c(m, 2);
c(m, 1);
ans[m][1]++;
dfsn(2);
}
}
else if (Chess[line - 1][num]==1 && Chess[line][num - 1]==1 && back1(num)==1)
{
c(line - 1 , num);
c(line, num - 1);
c(line, num + 1);
c(line, num);
ans[line][num]++;
dfsn(num + 1);
/*
ans[line][num]--;
c(line - 1, num);
c(line, num - 1);
c(line, num + 1);
c(line, num);
*/
}
else if (Chess[line - 1][num] == 0 && Chess[line - 1][num] == 0 && back2(num) == 0)
dfsn(num + 1);
}
void dfs(int line, int num)
{
if (num == n + 1 && line == m - 1)
{
dfsn(1);
return ;
}
if (num == n + 1)
{
dfs(line + 1, 1);
return ;
}
if (Chess[line - 1][num] == 0)
dfs(line, num + 1);
else
{
c(line - 1, num);
c(line + 1, num);
c(line, num - 1);
c(line, num + 1);
c(line, num);
ans[line][num]++;
dfs(line, num + 1);
/*
ans[line][num]--;
c(line - 1, num);
c(line + 1, num);
c(line, num - 1);
c(line, num + 1);
c(line, num);
*/
}
}
void firstLineS(int k)
{
if (k == n + 1)
{
if (m > 2)
dfs(2, 1);
else if (m == 2)
dfsn(1);
return ;
}
firstLineS(k + 1);
c(1, k);
c(1, k - 1);
c(1, k + 1);
c(2, k);
ans[1][k]++;
firstLineS(k + 1);
ans[1][k]--;
c(1, k);
c(1, k - 1);
c(1, k + 1);
c(2, k);
}
void dfs1(int num)
{
if (num == m + 1)
{
print();
return ;
}
if (num == 1)
{
dfs1(num + 1);
ans[num][1]++;
c(num, 1);
c(num + 1, 1);
dfs1(num + 1);
ans[num][1]--;
c(num, 1);
c(num + 1, 1);
}
if(Chess[num - 1][1] == 0)
dfs1(num + 1);
else {
ans[num][1]++;
c(num, 1);
c(num + 1, 1);
c(num - 1, 1);
dfs1(num + 1);
ans[num][1]--;
c(num + 1, 1);
c(num - 1, 1);
c(num, 1);
}
}
int main()
{
cin >> m>> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> Chess[i][j];
if (m == 1) dfsn(1);
if (n == 1) dfs1(1);
firstLineS(1);
if (minans==99999)
cout<<"IMPOSSIBLE"<<endl;
else
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
cout << minan[i][j]%2<<" ";
cout << endl;
}
return 0;
}
[/collapse]