目录
试题 A: 星期计算
本题总分：5 分
【问题描述】
已知今天是星期六，请问? 天后是星期几？
注意用数字 1 到 7 表示星期一到星期日。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
【解析】运行结果是1，6+1=7
【答案】7
public class Main {
public static void main(String[] args) {
int n = (int) (Math.pow(20, 22) % 7);
System.out.println(n);
}
}试题 B: 山
本题总分：5 分
【问题描述】
这天小明正在学数数。
他突然发现有些正整数的形状像一座“山”，比如 123565321、145541，它们左右对称（回文）且数位上的数字先单调不减，后单调不增。
小明数了很久也没有数完，他想让你告诉他在区间 [2022, 2022222022] 中有多少个数的形状像一座“山”。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
【解析】求[2022, 2022222022]中先单调不减，后单调不增的数的数量
【答案】3138
public class Main{
public static void main(String[] args) {
long ans=0;
for(long i=2022;i<=2022222022;i++) {
if(check(i)) {
ans++;
}
}
System.out.println(ans);
}
private static boolean check(long i) {
//判断是否回文
String string = String.valueOf(i);
StringBuilder sBuilder = new StringBuilder(string);
if(string.compareTo(sBuilder.reverse().toString())==0) { //是回文数
for(int j=0;j<string.length()/2;j++) {
int pre = Integer.valueOf(string.charAt(j));
int aft = Integer.valueOf(string.charAt(j+1));
if(aft<pre)
return false;
}
return true;
}
return false;
}
}试题 C: 字符统计
时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分
【问题描述】
给定一个只包含大写字母的字符串 S ，请你输出其中出现次数最多的字母。如果有多个字母均出现了最多次，按字母表顺序依次输出所有这些字母。
【输入格式】
一个只包含大写字母的字符串 S .
【输出格式】
若干个大写字母，代表答案。
【样例输入】
BABBACAC
【样例输出】
AB
【评测用例规模与约定】
对于 100% 的评测用例，1 ≤ |S | ≤ .
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] ch = sc.nextLine().toCharArray();
int[] arr = new int[128];
for(int i=0;i<ch.length;i++) {
arr[ch[i]]++;
}
int max = 0;
StringBuffer sb = new StringBuffer();
//得出出现最多次数的个数
for(int i=0;i<arr.length;i++) {
if(arr[i]>max) {
max = arr[i];
}
}
//把出现次数最多的字符按照字典顺序组合
for(int i=65;i<128;i++) {
if(arr[i]==max) {
sb.append((char)i);
}
}
System.out.println(sb);
}
}试题 D: 最少刷题数
时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分
【问题描述】
小蓝老师教的编程课有 N 名学生，编号依次是 1 . . . N。第 i 号学生这学期刷题的数量是 Ai。
对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。
【输入格式】
第一行包含一个正整数 N。
第二行包含 N 个整数：A1, A2, A3, . . . , AN.
【输出格式】
输出 N 个整数，依次表示第 1 . . . N 号学生分别至少还要再刷多少道题。
【样例输入】
5
12 10 15 20 6
【样例输出】
0 3 0 0 7
【评测用例规模与约定】
对于 30% 的数据，1 ≤ N ≤ 1000, 0 ≤ Ai ≤ 1000.
对于 100% 的数据，1 ≤ N ≤ 100000, 0 ≤ Ai ≤ 100000.
解法一
中位数求解，但是没有考虑到边界问题，可能只过了部分样例，不能得满分。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] A = new int[N];
for(int i = 0;i < N;i++) {
A[i] = sc.nextInt();
}
int[] B = new int [N];
for(int i = 0;i < N;i++) {
B[i] = A[i];
}
zhongwei(A);
for(int j = 0;j < N;j++) {
if(B[j] >= n) {
System.out.print(0 + " ");
}
if(B[j] < n) {
System.out.print(n - B[j] + 1 + " ");
}
}
}
private static int zhongwei(int[] A) {
int c = A.length;
Arrays.sort(A);
if(A.length % 2 == 1) {
return n = A[A.length / 2];
}
if(A.length % 2 == 0) {
return n = (A[A.length/2]+A[A.length/2 + 1]) / 2;
}
return n;
}
}解法二
import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N=sc.nextInt();
int[] arr = new int[N];
int[] find = new int[N];
for(int i = 0;i < N;i++) {
int num = sc.nextInt();
arr[i]=num;
find[i]=num;
}
Arrays.sort(find);
for(int i = 0;i < N;i++) {
//在find中查找arr[i]的位置
int pos = Arrays.binarySearch(find, arr[i]);
//计算其左边的数
int less = pos;
int more = N-pos-1;
if(more > less) { //刷题多的多余刷题少的
int d = more-less;
int num = find[pos+d/2]-find[pos]+1;
System.out.print(num+" ");
}else {
System.out.print(0+" ");
}
}
}
}试题 E: 求阶乘
时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分
【问题描述】
满足 N! 的末尾恰好有 K 个 0 的最小的 N 是多少?如果这样的 N 不存在输出 ?1。
【输入格式】
一个整数 K。
【输出格式】
一个整数代表答案。
【样例输入】
2
【样例输出】
10
【评测用例规模与约定】
对于 30% 的数据，1 ≤ K ≤ .
对于 100% 的数据，1 ≤ K ≤ .
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long K = sc.nextLong();
long L = 5, R = K * 5, M, T = 0;
while (L <= R) {
M = L + R >> 1; T = 0;
for (long I = 5; I <= M; I *= 5) T += M / I;
if (T == K) {
System.out.println(M - M % 5);
return;
}
if (T < K) L = M + 1; else R = M - 1;
}
System.out.println("-1");
}
}试题 F: 最大子矩阵
时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分
【问题描述】
小明有一个大小为 N × M 的矩阵，可以理解为一个 N 行 M 列的二维数组。我们定义一个矩阵 m 的稳定度 f (m) 为 f (m) = max(m) ? min(m)，其中 max(m)表示矩阵 m 中的最大值，min(m) 表示矩阵 m 中的最小值。现在小明想要从这个矩阵中找到一个稳定度不大于 limit 的子矩阵，同时他还希望这个子矩阵的面积越大越好（面积可以理解为矩阵中元素个数）。
子矩阵定义如下：从原矩阵中选择一组连续的行和一组连续的列，这些行列交点上的元素组成的矩阵即为一个子矩阵。
【输入格式】
第一行输入两个整数 N，M，表示矩阵的大小。
接下来 N 行，每行输入 M 个整数，表示这个矩阵。最后一行输入一个整数 limit，表示限制。
【输出格式】
输出一个整数，分别表示小明选择的子矩阵的最大面积。
【样例输入】
3 4
2 0 7 9
0 6 9 7
8 4 6 4
8【样例输出】
6【样例说明】
满足稳定度不大于 8 的且面积最大的子矩阵总共有三个，他们的面积都是
6（粗体表示子矩阵元素）：
2 0 7 9
0 6 9 7
8 4 6 4
2 0 7 9
0 6 9 7
8 4 6 4
2 0 7 9
0 6 9 7
8 4 6 4
【评测用例规模与约定】
?对于所有评测用例，0 ≤ 矩阵元素值, limit ≤ 。
import java.util.Scanner;
public class Main{
static int[][] arr;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
arr=new int[N][M];
for(int i = 0;i < N;i++) {
for(int j = 0;j < M;j++) {
arr[i][j]=sc.nextInt();
}
}
int limit = sc.nextInt();
int max_are = Integer.MIN_VALUE;
for(int i = N;i > 0;i--) {
for(int j = M;j > 0;j--) { // i*j的矩阵
for(int x = 0;x <= N-i;x++) {
for(int y = 0;y <= M-j;y++) { //左上角坐标
int max = find_max(i,j,x,y);
int min = find_min(i,j,x,y);
if((max-min) <= limit) {
max_are = Math.max(max_are, i*j);
// System.out.println(x+" "+y+" "+" "+i+" "+j);
// System.out.println(i*j);
// return;
}
}
}
}
}
System.out.println(max_are);
}
private static int find_min(int i, int j, int x, int y) {
//寻找最小值
int res = Integer.MAX_VALUE;
for(int n = x;n < x+i;n++) {
for(int m = y;m < y+j;m++) {
res = Math.min(res, arr[n][m]);
}
}
return res;
}
private static int find_max(int i, int j, int x, int y) {
//寻找最大值
int res = Integer.MIN_VALUE;
for(int n = x;n < x+i;n++) {
for(int m = y;m < y+j;m++) {
res = Math.max(res, arr[n][m]);
}
}
return res;
}
}试题 G: 数组切分
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
【问题描述】
已知一个长度为 N 的数组：A1, A2, A3, …AN 恰好是 1 ～ N 的一个排列。现在要求你将 A 数组切分成若干个 (最少一个，最多 N 个) 连续的子数组，并且每个子数组中包含的整数恰好可以组成一段连续的自然数。
例如对于 A = {1, 3, 2, 4}, 一共有 5 种切分方法：
{1}{3}{2}{4}：每个单独的数显然是 (长度为 1 的) 一段连续的自然数。
{1}{3, 2}{4}：{3, 2} 包含 2 到 3，是 一段连续的自然数，另外 {1} 和 {4} 显然也是。
{1}{3, 2, 4}：{3, 2, 4} 包含 2 到 4，是 一段连续的自然数，另外 {1} 显然也是。
{1, 3, 2}{4}：{1, 3, 2} 包含 1 到 3，是 一段连续的自然数，另外 {4} 显然也是。
{1, 3, 2, 4}：只有一个子数组，包含 1 到 4，是 一段连续的自然数。
【输入格式】
第一行包含一个整数 N。第二行包含 N 个整数，代表 A 数组。
【输出格式】
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值
【样例输入】
4
1 3 2 4【样例输出】
5【评测用例规模与约定】
对于 30% 评测用例，1 ≤ N ≤ 20.
对于 100% 评测用例，1 ≤ N ≤ 10000.
解法一
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;
public class Main {
public static void main(String[] args) {
int p = 1000000007;
int n = nextInt(), max, min;
int[] A = new int[n + 1];
int[] f = new int[n + 1];
f[0] = 1;
for (int i = 1; i <= n; ++i) {
max = min = A[i] = nextInt();
for (int j = i; j > 0; --j) {
if (A[j] > max) max = A[j];
if (A[j] < min) min = A[j];
if (i - j == max - min)
f[i] = (f[i] + f[j - 1]) % p;
}
}
System.out.println(f[n]);
}
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int nextInt() {
try {
in.nextToken();
} catch (IOException e) {
e.printStackTrace();
}
return (int)in.nval;
}
}解法二
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static boolean[] vis;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] arr = new int[N];
vis = new boolean[N];
for (int i = 0; i < N; i++) {
arr[i] = scanner.nextInt();
}
long ans = DFS(arr, 0);
System.out.println(ans);
}
private static long DFS(int[] arr, int k) {
if (k == arr.length-1) {
if (check(arr)) {
// for(int i=0;i<vis.length;i++) {
// System.out.print(vis[i] + " ");
// }
// System.out.println();
return 1;
}
return 0;
}
// 当前位置切
int res = 0;
vis[k] = true;
res += DFS(arr, k + 1);
// 当前位置不切
vis[k] = false;
res += DFS(arr, k + 1);
return res;
}
private static boolean check(int[] arr) {
//检查当前切法是否符合规则
int len = arr.length;
int p = 0;
int q = 1;
while (q < len) {
if (vis[q - 1]) {
if (!check_lianxu(arr, p, q)) {
return false;
}
p=q;
}
q++;
}
if(!check_lianxu(arr, p, q)) {
return false;
}
return true;
}
private static boolean check_lianxu(int[] arr, int p, int q) {
// 检测数组是否连续p-q
int[] arrcopy = new int[q-p];
System.arraycopy(arr, p, arrcopy, 0, q-p);
Arrays.sort(arrcopy);
for(int i=0;i<q-p-1;i++) {
if(arrcopy[i+1]-arrcopy[i]!=1) {
return false;
}
}
return true;
}
}试题 H: 回忆迷宫
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
【问题描述】
爱丽丝刚从一处地下迷宫中探险归来，你能根据她对于自己行动路径的回忆，帮她画出迷宫地图吗？
迷宫地图是基于二维网格的。爱丽丝会告诉你一系列她在迷宫中的移动步骤，每个移动步骤可能是上下左右四个方向中的一种，表示爱丽丝往这个方向走了一格。你需要根据这些移动步骤给出一个迷宫地图，并满足以下条件：
1、爱丽丝能在迷宫内的某个空地开始，顺利的走完她回忆的所有移动步骤。
2、迷宫内不存在爱丽丝没有走过的空地。
3、迷宫是封闭的，即可通过墙分隔迷宫内与迷宫外。任意方向的无穷远处视为迷宫外，所有不与迷宫外联通的空地都视为是迷宫内。（迷宫地图为四联通，即只有上下左右视为联通）
4、在满足前面三点的前提下，迷宫的墙的数量要尽可能少。
【输入格式】
第一行一个正整数 N，表示爱丽丝回忆的步骤数量。
接下来一行 N 个英文字符，仅包含 UDLR 四种字符，分别表示上（Up）、下（Down）、左（Left）、右（Right）。
【输出格式】
请通过字符画的形式输出迷宫地图。迷宫地图可能包含许多行，用字符 ‘’
表示墙，用 ‘ ’（空格）表示非墙。你的输出需要保证以下条件：
1、至少有一行第一个字符为 ‘’。
2、第一行至少有一个字符为 ‘*’。
3、每一行的最后一个字符为 ‘’。
4、最后一行至少有一个字符为 ‘’。
【样例输入】
17
UUUULLLLDDDDRRRRU
【样例输出】
*****
* *
* *** *
* *** *
* *** *
* *
*****【样例说明】
爱丽丝可以把第六行第六个字符作为起点。外墙墙墙墙墙外
墙内内内内内墙
墙内墙墙墙内墙墙内墙墙墙内墙墙内墙墙墙内墙墙内内内内内墙外墙墙墙墙墙外
【评测用例规模与约定】
对于所有数据，0 < N ≤ 100.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) { new Main().run(); }
int N = 333, M = 333, x = 111, y = 111, x1 = x, y1 = y, x2 = x, y2 = y;
int[][] offset = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
byte[][] ans = new byte[N][M];
void run() {
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j) ans[i][j] = '$';
try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out)) {
int n = Integer.parseInt(in.readLine());
String line = in.readLine();
step(x, y);
for (int i = 0; i < n; ++i) {
switch (line.charAt(i)) {
case 'U': step(--x, y); break;
case 'R': step(x, ++y); break;
case 'D': step(++x, y); break;
case 'L': step(x, --y);
}
if (x < x1) x1 = x;
if (y < y1) y1 = y;
if (x > x2) x2 = x;
if (y > y2) y2 = y;
}
Deque<Long> queue = new ArrayDeque();
queue.offer(makePair(0, 0));
while (!queue.isEmpty()) {
int x = X(queue.peek());
int y = Y(queue.peek());
queue.poll();
if (x < 0 || x >= N || y < 0 || y >= M || ans[x][y] != '$') continue;
ans[x][y] = ' ';
for (int i = 0; i < 4; ++i)
queue.offer(makePair(x + offset[i][0], y + offset[i][1]));
}
--x1; ++x2; --y1; ++y2;
for (; x1 <= x2; ++x1) {
int space = 0;
for (int y = y1; y <= y2; ++y)
if (ans[x1][y] == ' ') ++space;
else {
for (; space > 0; --space)
out.write(' ');
out.write('*');
}
out.write('\n');
}
} catch (IOException e) {
e.printStackTrace();
}
}
long makePair(int x, int y) { return (long)x << 32 | y; }
int X(long pair) { return (int)(pair >>> 32); }
int Y(long pair) { return (int)pair; }
void step(int x, int y) {
ans[x][y] = ' ';
for (int i = 0; i < 4; ++i)
if (ans[x + offset[i][0]][y + offset[i][1]] == '$')
ans[x + offset[i][0]][y + offset[i][1]] = '*';
}
}试题 I: 红绿灯
时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
【问题描述】
爱丽丝要开车去上班，上班的路上有许多红绿灯，这让爱丽丝很难过。为了上班不迟到，她给自己的车安装了氮气喷射装置。现在她想知道自己上班最短需要多少时间。
爱丽丝的车最高速度是 1 米每秒，并且经过改装后，可以瞬间加速到小于
等于最高速的任意速度，也可以瞬间停止。
爱丽丝家离公司有 N 米远，路上有 M 个红绿灯，第 i 个红绿灯位于离爱丽丝家 Ai 米远的位置，绿灯持续 Bi 秒，红灯持续 Ci 秒。在初始时（爱丽丝开始计时的瞬间），所有红绿灯都恰好从红灯变为绿灯。如果爱丽丝在绿灯变红的瞬间到达红绿灯，她会停下车等红灯，因为她是遵纪守法的好市民。
氮气喷射装置可以让爱丽丝的车瞬间加速到超光速（且不受相对论效应的影响！），达到瞬移的效果，但是爱丽丝是遵纪守法的好市民，在每个红绿灯前她都会停下氮气喷射，即使是绿灯，因为红绿灯处有斑马线，而使用氮气喷射装置通过斑马线是违法的。此外，氮气喷射装置不能连续启动，需要一定时间的冷却，表现为通过 K 个红绿灯后才能再次使用。（也就是说，如果 K = 1，就能一直使用啦！）初始时，氮气喷射装置处于可用状态。
【输入格式】
第一行四个正整数 N、M、K、V，含义如题面所述。
接下来 M 行，每行三个正整数 Ai、Bi、Ci，含义如题面所述。
【输出格式】
输出一个正整数 T，表示爱丽丝到达公司最短需要多少秒。
【样例输入】
90 2 2 2
30 20 20
60 20 20【样例输出】
80【样例说明】
爱丽丝在最开始直接使用氮气喷射装置瞬间到达第一个红绿灯，然后绿灯通过，以最高速行进 60 秒后到达第二个红绿灯，此时绿灯刚好变红，于是她等
待 20 秒再次变为绿灯后通过该红绿灯，此时氮气喷射装置冷却完毕，爱丽丝再
次使用瞬间到达公司，总共用时 80 秒。
【评测用例规模与约定】
对于 30% 的数据，N ≤ 100; M ≤ 10; M < K; V = 1.
对于 60% 的数据，N ≤ 1000; M ≤ 100; K ≤ 50; Bi, Ci ≤ 100; V ≤ 10.
对于 100% 的数据，0 < N ≤ 108; M ≤ 1000; K ≤ 1000; 0 < Bi, Ci ≤ 106; 0 <
V ≤ 106; 0 < Ai < N; 对任意 i < j, 有 Ai < Aj.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;
import java.io.IOException;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt(), v = sc.nextInt();
int[] A = new int[m + 2], B = new int[m + 1], C = new int[m + 1];
long[][] dp = new long[m + 1][k + 1];
for (int i = 1; i <= m; ++i) {
A[i] = sc.nextInt();
B[i] = sc.nextInt();
C[i] = sc.nextInt();
}
A[m + 1] = n;
for (int i = 0; i < k; ++i)
dp[0][i] = A[1] * (long)v;
for (int i = 1; i <= m; ++i) {
dp[i][k] = min(dp[i - 1][0], dp[i - 1][1]);
if (dp[i][k] % (B[i] + C[i]) >= B[i])
dp[i][k] += B[i] + C[i] - dp[i][k] % (B[i] + C[i]);
dp[i][0] = dp[i][k] + (A[i + 1] - A[i]) * (long)v;
for (int j = 1; j < k; ++j) {
dp[i][j] = dp[i - 1][j + 1] + (A[i + 1] - A[i]) * (long)v;
if (dp[i - 1][j + 1] % (B[i] + C[i]) >= B[i])
dp[i][j] += B[i] + C[i] - dp[i - 1][j + 1] % (B[i] + C[i]);
dp[i][j] = min(dp[i][j], dp[i][j - 1]);
}
}
long ans = dp[m][0];
for (int i = 1; i <= k; ++i)
ans = min(ans, dp[m][i]);
System.out.println(ans);
}
static long min(long arg1, long arg2) { return arg1 < arg2 ? arg1 : arg2; }
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
}试题 J: 拉箱子
时间限制: 1.0s 内存限制: 1.0GB 本题总分：25 分
【问题描述】
推箱子是一款经典电子游戏，爱丽丝很喜欢玩，但是她有点玩腻了，现在她想设计一款拉箱子游戏。
拉箱子游戏需要玩家在一个 N × M 的网格地图中，控制小人上下左右移动，将箱子拉到终点以获得胜利。
现在爱丽丝想知道，在给定地形（即所有墙的位置）的情况下，有多少种不同的可解的初始局面。
【初始局面】 的定义如下：
1、初始局面由排列成 N × M 矩形网格状的各种元素组成，每个网格中有且只有一种元素。可能的元素有：空地、墙、小人、箱子、终点。
2、初始局面中有且只有一个小人。
3、初始局面中有且只有一个箱子。
4、初始局面中有且只有一个终点。
【可解】 的定义如下：
通过有限次数的移动小人（可以在移动的同时拉箱子），箱子能够到达终点所在的网格。
【移动】 的定义如下：
在一次移动中，小人可以移动到相邻（上、下、左、右四种选项）的一个网格中，前提是满足以下条件：
1、小人永远不能移动到 N × M 的网格外部。
2、小人永远不能移动到墙上或是箱子上。
3、小人可以移动到空地或是终点上。
【拉箱子】 的定义如下：
在一次合法移动的同时，如果小人初始所在网格沿小人移动方向的反方向
上的相邻网格上恰好是箱子，小人可以拉动箱子一起移动，让箱子移动到小人初始所在网格。
即使满足条件，小人也可以只移动而不拉箱子。
【输入格式】
第一行两个正整数 N 和 M，表示网格的大小。
接下来 N 行，每行 M 个由空格隔开的整数 0 或 1 描述给定的地形。其中 1 表示墙，0 表示未知的元素，未知元素可能是小人或箱子或空地或终点，但不能是墙。
【输出格式】
输出一个正整数，表示可解的初始局面数量。
【样例输入】
2 4
0 0 0 0
1 1 1 0【样例输出】
13【样例说明】
13 种可解的初始局面示意图如下：
人终箱空墙墙墙空
********人终空箱墙墙墙空
人空终箱
墙墙墙空
********箱人终空墙墙墙空
********空人终箱墙墙墙空
********箱终人空墙墙墙空
********空终人箱墙墙墙空
********箱终空人墙墙墙空
********箱空终人墙墙墙空
********空箱终人墙墙墙空
********箱终空空墙墙墙人
********箱空终空墙墙墙人
********空箱终空墙墙墙人
【评测用例规模与约定】
对于 30% 的数据，N, M ≤ 3.
对于 100% 的数据，0 < N, M ≤ 10.
?
