Wddpdh find an interesting mini-game in the BBS of WHU, called “An easy PUZ”. It’s a 6 * 6 chess board and each cell has a number in the range of 0 and 3(it can be 0, 1, 2 or 3). Each time you can choose a number A(i, j) in i-th row and j-th column, then the number A(i, j) and the numbers around it (A(i-1, j), A(i+1, j),A(i, j-1),A(i, j+1), sometimes there may just be 2 or 3 numbers.) will minus 1 (3 to 2, 2 to 1, 1 to 0, 0 to 3). You can do it finite times. The goal is to make all numbers become 0. Wddpdh now come up with an extended problem about it. He will give you a number N (3 <= N <= 6) indicate the size of the board. You should tell him the minimum steps to reach the goal.

The input consists of multiple test cases. For each test case, it contains a positive integer N(3 <= n <= 6). N lines follow, each line contains N columns indicating the each number in the chess board.

For each test case, output minimum steps to reach the goal. If you can’t reach the goal, output -1 instead.

 #include<bits/stdc++.h>

 using namespace std;

 int n,a[][],c[][],b[],minn;

 int dx[]={,,,,-};

 int dy[]={,-,,,};

 void dfs(int p,int ans)

 {

     if(p==n+)

     {

         for(int i=;i<=n;i++)for(int j=;j<=n;j++)c[i][j]=a[i][j];

         for(int j=;j<=n;j++)

             for(int k=;k<;k++)

             {

                 int xx=+dx[k];

                 int yy=j+dy[k];

                 if(xx>=&&xx<=n&&yy>=&&yy<=n)c[xx][yy]=(c[xx][yy]-b[j]+)%;

             }

         for(int i=;i<=n;i++)

             for(int j=;j<=n;j++)

                 if(c[i-][j])

                 {

                     ans+=c[i-][j];

                     for(int k=;k<;k++)

                     {

                         int xx=i+dx[k];

                         int yy=j+dy[k];

                         if(xx>=&&xx<=n&&yy>=&&yy<=n)c[xx][yy]=(c[xx][yy]-c[i-][j]+)%;

                     }

                 }

         for(int i=;i<=n;i++)

             for(int j=;j<=n;j++)

                 if(c[i][j])

                     goto e;

         minn=min(minn,ans);

         e:return;

     }

     for(int i=;i<;i++)

     {

         b[p]=i;

         dfs(p+,ans+i);

     }

 }

 int main()

 {

     while(scanf("%d",&n)!=EOF)

     {

         for(int i=;i<=n;i++)for(int j=;j<=n;j++)scanf("%d",&a[i][j]);

         minn=1e9;

         dfs(,);

         printf("%d\n",minn==1e9?-:minn);

     }

     return ;

 }