HMMT 十一月 2018 · 冲刺赛 · 第 36 题
HMMT November 2018 — Guts Round — Problem 36
题目详情
英文原题
- [ 20 ] An n × m maze is an n × m grid in which each cell is one of two things: a wall, or a blank. A mazeis solvable if there exists a sequence of adjacent blank cells from the top left cell to the bottom rightcell going through no walls. (In particular, the top left and bottom right cells must both be blank.)
Let N be the number of solvable 5 × 5 mazes. Estimate N .
( )
N E2
An estimate of E > 0 earns b 20 min , c points.
E N
解析
英文解析
- [ 20 ] An n ⇥ m maze is an n ⇥ m grid in which each cell is one of two things: a wall, or a blank. A mazeis solvable if there exists a sequence of adjacent blank cells from the top left cell to the bottom rightcell going through no walls. (In particular, the top left and bottom right cells must both be blank.)
Let N be the number of solvable 5 ⇥ 5 mazes. Estimate N .
N E2
An estimate of E > 0 earns b 20 min , c points.
E N
Proposed by: John Michael Wu
Answer: 1225194
The following code solves the problem in Python 3.
dfs that returns all paths with no adjacent vertices other than those consecutive in the pathdef dfs(graph,start,end,path):
if start==end:
return [path]
paths=[]
for child in graph[start]:
skip=Falseif child in path:
continuefor vert in graph[child]:
if vert in path[:-1]:
skip=Truebreakif not skip:
paths=paths+dfs(graph,child,end,path[:]+[child])
return paths
construct graph representing 5 x 5 gridgraph={}
for a in range(5):
for b in range(5):
graph[(a,b)]=[]
for a in range(4):
for b in range(5):
graph[(a,b)].append((a+1,b));graph[(a+1,b)].append((a,b))
graph[(b,a)].append((b,a+1));graph[(b,a+1)].append((b,a))
paths=dfs(graph,(0,0),(4,4),[(0,0)])
paths.sort(key=len)
intpaths=[0]*len(paths)
convert paths to 25-bit binary integersfor i in range(len(paths)):
for j in paths[i]:
intpaths[i]+=2**(5j[0]+j[1])
mazes=0
for j in range(2**23):
k=2j
disregard cases that are common and never validif k&8912896==8912896 or k&34==34 or k&4472832==4472832 or k&1092==1092:
continuefor path in intpaths:
cehck if case has empty spaces along whole pathif path&k==0:
mazes+=1
breakprint(mazes)
Alternatively, the following code solves the problem in Java SE 8.
import java.util.*;
public class guts 36 {
static int M = 5;
static int N = 5;
static long[] pow 2 = new long[M * N];
static int[][] dir = new int[][] {new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[]
public static void main(String[] args) {
pow 2[0] = 1;
for (int i = 1; i < pow 2.length; i++) {
pow 2[i] = pow 2[i - 1] * 2;
}
boolean[][] grid = new boolean[M][N];
grid[0][0] = true;
grid[M - 1][N - 1] = true;
int ans = 0;
for (long c = 0; c < pow 2[M * N - 2]; c++) {
long d = c;
for (int b = 0; b < M * N - 2; b++) {
int i = (b + 1) / N;
int j = (b + 1) % N;
grid[i][j] = ((d & 1) > 0);
d >>= 1;
}
if (check(grid)) {
ans++;
}
}
System.out.println("answer: " + ans);
}
static int[] add(int[] a, int[] b) {
return new int[] {a[0] + b[0], a[1] + b[1]};
}
static boolean get(boolean[][] g, int[] a) {
return g[a[0]][a[1]];
}
static void set(boolean[][] g, int[] a, boolean v) {
g[a[0]][a[1]] = v;
}
static boolean valid(int[] a) {
return (a[0] >= 0) && (a[1] >= 0) && (a[0] < M) && (a[1] < N);
}
static boolean check(boolean[][] grid) {
Stack<int[]> q = new Stack<int[]>();
q.add(new int[] {0, 0});
boolean[][] reached = new boolean[M][N];
reached[0][0] = true;
while (!q.is empty()) {
int[] a = q.pop();
for (int[] d: dir) {
int[] b = add(a, d);
if (valid(b) && get(grid, b) && !get(reached, b)) {
if (b[0] == M - 1 && b[1] == N - 1) {
return true;
}
set(reached, b, true);
q.add(b);
}
}
}
return false;
}
}