题目描述

农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

输入格式
第一行：两个整数M和N，用空格隔开。

第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。

输出格式
一个整数，即牧场分配总方案数除以100,000,000的余数。

输入输出样例
输入
2 3
0 1 1
1 1 0
输出
8

import java.util.Scanner;public class CodingExam {private static int res = 0;  // 记录方案数private static int[] dx = {-1,1,0,0};  // 上下左右 四个方向private static int[] dy = {0,0,-1,1};public static void main(String[] args) {Scanner sc = new Scanner(System.in);int M = sc.nextInt();  // M行int N = sc.nextInt();   // N列String line = sc.nextLine();  // 读取空行int[][] a = new int[M][N];for (int i=0;i<M;i++) {String[] nums = sc.nextLine().split(" ");for (int j=0;j<N;j++) {a[i][j] = Integer.parseInt(nums[j]);}}solve(a);int mod = 100000000;res = res % mod;System.out.println(res);}public static void solve(int[][] a) {boolean[][] vis = new boolean[a.length][a[0].length];  // 访问记录数组dfs(a, 0, 0, vis);}public static void dfs(int[][] a, int r, int c, boolean[][] v) {// 判断不满足条件的情况boolean flag = true;   // flag表示当前情况是否可行if (a[r][c] == 1) {    // 当a[r][c]=1时，表示可以种植，需要判断如果它种植了，会不会和上下左右四个方向的其他种植点冲突，如果冲突了，flag=false,需要和a[r][c]=0的情况一起处理for (int i=0;i<4 && flag;i++) {int tmpR = r + dx[i];int tmpC = c + dy[i];// 边界出了不影响flag 继续搜索其他方向if (tmpR >= 0 && tmpR < a.length && tmpC >=0 && tmpC < a[0].length && v[tmpR][tmpC] && a[tmpR][tmpC] == 1) {flag = false;}}}// 每行每列搜 注意换行int nextR = r;  // 下次搜索的行int nextC = c + 1;   // 下次搜索的列if (nextC == a[0].length) {nextR = nextR + 1;    // 换行nextC = 0;            // 列更新为0}if (nextR == a.length) {   // 结束条件res++;      // 记录结果return;}// 判断 位置是1或0if (a[r][c] == 0 || !flag) {  // 条件：1.当前位置a[r][c]=0,不能种 2.当前位置a[r][c]=1,但是flag=falsedfs(a, nextR, nextC, v);}else {              // 如果 当前位置a[r][c]=1 则有两种选择 种/不种dfs(a, nextR, nextC, v);  // 不种v[r][c] = true;  // 种dfs(a, nextR, nextC, v);v[r][c] = false;  // 恢复现场}}}