## 1 Introduction  
Pursuit-evasion problems have a long history in mathematics and computer science, and many different models have been studied. At SoCG'07, [PERSON] _et al._[6] introduced a variant that has, apparently, not received much attention before. There are two different ways to consider this problem. The first approach, used by [PERSON], is to regard it as a pursuit-evasion problem. Then, the situation is that we have a pride of lions prowling among the vertices and edges of a \(d\)-dimensional \(n\times\ldots\times n\) grid. If their paths are known in advance, is it possible to design a safe path for a man that avoids all lions, assuming that man and lion move simultaneously and at the same speed along the graph edges? To be more precise, let \(G\) denote the \(d\)-dimensional \(n\times\ldots\times n\) grid with vertex set \(V\). A path \(\pi\) visiting \(p\in V\) at time \(t\in\{0,\ldots,T-1\}\) may visit a direct neighbor \(q\) of \(p\) at time \(t+1\), or remain at \(p\). Two paths \(\pi_{1},\pi_{2}\) are said to avoid each other if they never occupy the same vertex at the same time \(t\) and, in their transition from \(t\) to \(t+1\), never traverse the same grid edge from opposite sides. Now the problem is the following. What is the maximum number \(k=k_{d}(n)\) such that for all possible sets of \(k\) \"lion\" paths with arbitrary length \(T\) in \(G\) one can construct a \"man\" path that avoids them all? For such games, there are many different denotations for the pursuer and the haunted in the literature. Besides _lion and man_, also _cop and robber_ or _offline searcher and target_ are common terms. However, we prefer to take the _lion and man_ notation used by [PERSON]. The second approach to the problem above even makes the _man_ unnecessary. Instead of the path of one man, let us consider the set \(W(t)\) of all vertices where this man could be at time \(t\). That is, \(W(0)\) equals \(V\) minus the lions' start positions, and \(W(t+1)\) consists of all vertices \(p\) of \(V\) that  
* belong to \(W(t)\) and are not visited by a lion at time \(t+1\), or
* are not occupied by a lion at time \(t+1\), and have a direct neighbor \(q\) in \(W(t)\) that is not visited at time \(t+1\) by a lion coming directly from \(p\). Now, let us side with the lions! We may consider \(W(t)\) as the set of locations that are, at time \(t\), contaminated by some evil force that spreads one step per time unit in each direction not blocked by a lion. In this model, the lions' task is to fight contamination. A lion clears a contaminated vertex by visiting it. Once the lion is gone, the vertex may become recontaminated, according to the rules stated above. These definitions give rise to the following observation. A group of \(k\) lions is able to catch a man independently of how he moves if and only if they can shrink the set of contaminated vertices \(W(t)\) until it becomes the empty set. With this interpretation, our problem can be stated as follows. How many lions are needed to clear an initially contaminated \(n\times\ldots\times n\) grid? The problem considered differs from the classical man-and-lion problem introduced by [PERSON], see [PERSON] [10] or [PERSON] _et al._[1], where one lion knows the position of the man and moves in continuous time and space to catch him. Our problem also differs from the classical graph search problem introduced by [PERSON] [13], where the contamination would be allowed infinite speed. The literature of graph searching is much too broad to be summarized here, see [PERSON] [3] for a survey. It it is not clear how to adapt, to our problem, the proof of [PERSON]'s [8] result that a searchable graph can be searched optimally without recontamination. Considering our problem on arbitrary graphs instead of grid graphs, [PERSON] [12] found a planar graph where indeed allowing recontamination reduces the number of necessary lions in our setting.