算法1

(BFS) $O(1<<25)$

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 510;
int dx[5] = {-1,0,1,0,0},dy[5] = {0,1,0,-1,0};
char g[N][N];
int n ;
int mapp[1<<25];

int change(int temp,int x)//判断点周围有效性
{
    int t = temp;
    temp ^= 1 << x;
    if(x % 5!= 0) temp ^= 1 << (x-1);
    if(x % 5 !=4)temp ^= 1 << (x+1);
    if(x / 5 != 0) temp ^= 1<< (x-5);
    if(x /5 != 4) temp ^= 1 <<(x+5);
    if(mapp[temp] != -1) return -1;
    mapp[temp] = mapp[t] +1;
    return temp;

}
void bfs()
{
    int temp = (1 << 25) -1;
    queue<int> q;
    q.push(temp);
    memset(mapp,-1,sizeof mapp);
    mapp[temp] = 0;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        if(mapp[t] >= 6) continue;//这个状态6步 跳过找下一个
        for(int i = 0 ; i < 25; i ++)
        {
            int x = change(t,i);
            if(x == -1)continue;//重复状态
            q.push(x);

        }
    }

}

int main()
{
    //預處理所有初始状态
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    bfs();
    cin >> n;
    while(n--)
    {
        int index =0 ;
        string a;
        for(int i =0 ; i < 5; i ++)
        {

             cin >> a;
            for(int j = 0; j< 5; j ++)
            {
               index <<=1;
               index ^= (a[j]-'0');

            }
        }
        cout << mapp[index]<< endl;
    }
    return 0;
}