Necessary and Sufficient Condition

The necessary and sufficient condition of Yes is that one of the followings holds:

• \(H \ge W + 2\).
• \(H = W + 1\) and you use the magic first.

Sufficiency

Put the source \(s\) and the sink \(t\) at the left side and the right side, respectively, of the outside of the dungeon. Let each room be a vertex and each door be an edge, and then we obtain a graph \(G\). The question (your objective) is rephrased as follows. When you can contract each edge and merge the two end vertices into a single vertex, and DEGwer can delete each edge, can you eventually merge \(s\) and \(t\) into a single vertex?

Suppose that \(G\) has two edge-disjoint spanning trees \(T_1, T_2\). Then, the answer to the above question is Yes, which can be shown by induction as follows.

• If DEGwer chooses an edge not contained in \(T_1 \cup T_2\), then whichever edge you choose, the resulting graph clearly contains two edge-disjoint spanning trees.

• If DEGwer chooses an edge in \(T_i\), then after deleting that edge, \(T_i\) is divided into two connected components. Nevertheless, \(T_{3-i}\) contains an edge connecting these two components, so you can choose such an edge and contract it, the resulting graph contains two edge-disjoint spanning trees.

Since \(G\) is very special, symmetric graph, it is not so difficult to construct two edge-disjoint spanning trees when \(H \ge W + 2\). When \(H \ge W + 1\) and you use the magic first, by adding a virtual edge between \(s\) and \(t\), you can construct two edge-disjoint spanning trees, and then the situation can be regarded as when DEGwer chooses and deletes the virtual edge in this graph.

Necessity

Consider DEGwer’s situation. Actually, this is almost the same as yours by rotating the graph \(90^\circ\). Specifically, this is represented by a dual-like graph of \(G\), which is isomorphic to the graph \(G\) obtained from the dungeon with \((W + 1)\) rows and \((H - 1)\) columns. Thus, if the above condition does not hold, from this observation, it is shown that DEGwer’s objective is achievable.

Supplement

This game is known as Shannon switching game, which can be solved for general graphs in polynomial time with the aid of matroid intersection. DEGwer is familiar with matroid intersection (of course), so the interactor is implemented so that if he faces to a situation in which he can win, then he will definitely win. The computational time is \(\Theta(H^3 W^3)\), so this is heavier than the expected solution of this problem.