C++

#include <cstdio>

 

using namespace std;

int map_[30][30],N;

int check(int p,int s,int e, int t){

    int cnt=0;

    if(t==1){

       for(int i=s;i<=e;i++){

            if(map_[p][i]==2)

                return 0;

            if(map_[p][i]==1)

                cnt++;

       }

    }else{

        for(int i=s;i<=e;i++){

            if(map_[i][p]==2)

                return 0;

            if(map_[i][p]==1)

                cnt++;

       }

    }

    return cnt;

}

int serch(int x1,int y1,int x2,int y2,int t){

    int di=0,tr=0;

    for(int i=y1;i<=y2;i++){

        for(int j=x1;j<=x2;j++){

            if(map_[i][j]==1)

                tr++;

            if(map_[i][j]==2)

                di++;

        }

    }

    if(di==1&&tr==0)

        return 1;

    if(di==0||tr==0)

        return 0;

    int result=0;

    if(t){

        for(int i=y1;i<=y2;i++){

            if(check(i,x1,x2,t)){

                result+=serch(x1,y1,x2,i-1,0)*serch(x1,i+1,x2,y2,0);

            }

        }

    }

    else{

        for(int i=x1;i<=x2;i++){

            if(check(i,y1,y2,t)){

                result+=serch(x1,y1,i-1,y2,1)*serch(i+1,y1,x2,y2,1);

            }

        }

    }

    return result;

}

int main()

{

    scanf("%d",&N);

    for(int i=1;i<=N;i++){

        for(int j=1;j<=N;j++){

            scanf("%d",&map_[i][j]);

        }

    }

    int a;

    printf("%d",(a=serch(1,1,N,N,0)+serch(1,1,N,N,1))==0 ? -1:a);

    return 0;

}