题目在http://it.nankai.edu.cn/acm/nkpc3/problems/g.htm
我的方法是遍历,算法如下:
#include <stdio.h>
#include <stdbool.h>
#define MAX 5

int get( int n ); /*获得棋盘数据,利用2进制用一个整数表示棋盘*/

/*初始化position, 使position[i]表示对点( i / n, i % n )操作后的棋盘*/

void initial( int position[], int n );

int final( int n, int a, int b ); /* a和b分别表示初始棋盘和目标棋盘*/

int main( void )
{
    int i, n, count, tmp;
    int a, b;
    scanf( "%d%d", &n, &count );
    for ( i = 1; i <= count; ++i )
    {
        a = get( n );
        b = get( n );
        tmp = final( n, a, b );
        printf( "Case %d:\n", i );
        if ( tmp == -1 )
        {
            puts( "No Solution!" );
        }
        else
        {
            printf( "%d\n", tmp );
        }
    }
    return 0;
}

int final( int n, int a, int b )
{
    int i, top, input, sup;
    int bound = n * n;
    int stack[MAX * MAX];
    int position[MAX * MAX];
    int supbound;
    if ( n == 5 )
    {
        supbound = 17;
    }
    else if ( n == 4 )
    {
        supbound = 10;
    }
    else
    {
        supbound = n * n;
    }

    if ( a == b )
    {
        return 0;
    }
    initial( position, n );
    for ( i = 1; i <= supbound; ++i ) /*从操作1次遍历到操作supbound次*/
    {
        top = 0;
        input = 0;
        sup = bound - i + 1;
        while ( top > 0 || input < sup + top ) /*遍历组合C( i, bound )( 因为操作满足交换律 )*/
        {
            while ( top < i && input < sup + top )
            {
                stack[top++] = input;
                a ^= position[input++];
            }
            if ( top == i )
            {
                if ( a == b )
                {
                    return i;
                }
            }
            input = stack[--top];
            a ^= position[input++];
        }
    }
    return -1;
}

void initial( int position[], int n )
{
    int i;
    int row, line;
    int tmp;
    for ( i = 0; i < n * n; ++i ) /*i表示操作的位置,还算成row和line,然后tmp表示操作后的棋盘*/
    {
        tmp = 0;
        row = i / n;
        line = i % n;
        tmp += 1 << i;
        if ( row - 1 >= 0 )
        {
            tmp += 1 << i - n;
        }
        if ( row + 1 < n )
        {
            tmp += 1 << i + n;
        }
        if ( line - 1 >= 0 )
        {
            tmp += 1 << i - 1;
        }
        if ( line + 1 < n )
        {
            tmp += 1 << i + 1;
        }
        position[i] = tmp;
    }
}

int get( int n )
{
    int result, i, tmp;
    for ( i = 0, result = 0; i < n * n; ++i )
    {
        scanf( "%d", &tmp );
        if ( tmp == 1 )
        {
            result += 1 << i;
        }
    }
    return result;
}
不知道能不能不用遍历呢?