#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int a[5][5];
int vis[5][5]= {0};
int minn=20;
int cnt=0;
struct node
{
    int xx;
    int yy;
} ans[20],ans2[20];
int start;
bool finish()
{
    int n=0;
    for(int i=1; i<=4; i++)
    {
        for(int j=1; j<=4; j++)
        {
            if(a[i][j])
            {
                n++;
            }
        }
    }
    if(n%16==0)
        return true;
    else
        return false;
}
void change(int x,int y)
{
    for(int i=1; i<=4; i++)
    {
        a[x][i]=!a[x][i];
        a[i][y]=!a[i][y];
    }
    a[x][y]=!a[x][y];
}
void dfs(int x,int y,int count)
{
    if(finish())
    {
        if (count<minn)
        {
            minn=count;
            for(int i=0; i<minn; i++)
            {
                ans2[i].xx=ans[i].xx;
                ans2[i].yy=ans[i].yy;
            }
        }
        return;
    }
    if (count>16)
    {
        return;
    }
    for(int i=1; i<=4; i++)
    {
        for(int j=1; j<=4; j++)
        {
            if (vis[i][j]==0&&x*4+y<4*i+j)
            {
                vis[i][j]=1;
                change(i,j);
                ans[count].xx=i;
                ans[count].yy=j;
                dfs(i,j,count+1);
                change(i,j);
                vis[i][j]=0;
            }
        }
    }
}
int main()
{
    for(int i=0;i<20;i++)
    {
        ans[i].xx=0;
        ans[i].yy=0;
        ans2[i].xx=0;
        ans2[i].yy=0;
    }
    cnt=0;
    for(int i=1; i<=4; i++)
    {
        for(int j=1; j<=4; j++)
        {
            char ch;
            cin>>ch;
            if (ch=='-')
                a[i][j]=0;
            if (ch=='+')
                a[i][j]=1;
        }
    }
    dfs(0,0,0);

    cout<<minn<<endl;
    for(int i=0; i<minn; i++)
    {
        cout<<ans2[i].xx<<" "<<ans2[i].yy<<endl;
    }


    return 0;
}

• 简单的写法 (768) ACAccepted 2019-03-16 15:25:45