D - Takahashi the Wall Breaker 解説 by en_translator
Consider the following directed graph \(G\) corresponding to Takahashi’s town:
- Each vertex corresponds to a cell one-by-one. Notably, \(G\) has \((H\times W)\) vertices.
- From each cell \(C\) to each four-adjacent cell \(C'\) that is a road, add an edge of cost \(0\) from the vertex corresponding to \(C\) to that of \(C'\).
- From each cell \(C\) to each four-adjacent cell \(C'\) that is a wall, add an edge of cost \(1\) from the vertex corresponding to \(C\) to that of \(C'\).
- From each cell \(C\) to each cell \(C'\) that is two cells ahead of \(C\) in one of the four directions, if the cell in between or \(C'\) itself is a wall, add an edge of cost \(1\) from the vertex corresponding to \(C\) to that of \(C'\).
Then, the shortest distance in \(G\) from the vertex corresponding to Takahashi’s starting vertex to that of the fish shop (i.e. the minimum total weight of the edges in such a path) coincides with the answer.
Given a shortest path in \(G\), one can construct a sequence of Takahashi’s actions to travel from his initial vertex to the fish shop such that the number of front kicks is less than or equal to the shortest distance in \(G\), by interpreting a traversal of a weight-\(0\) edge as a move to a four-adjacent road cell, and a weight-\(1\) edge as a front kick followed by a move to a cell that has become a road.
On the other hand, one can prove by induction that, given a cell that can be reachable from his initial cell using at most \(k\) front kicks, one can construct a path in \(G\) from the vertex corresponding to his initial vertex to that of the given cell whose weight does not exceed \(k\).
Proof
It is obvious for $k=0$.
Assuming that it holds for $k=d-1$, we will consider $k=d$ case.
We promise that when we say a vertex is (un)reachable, the starting cell is Takahashi's initial cell.
Take a cell $T$ that is reachable by $d$ kicks and a specific sequence of actions to reach there with $d$ kicks.
There are $(d+1)$ kinds of states of the town: before performing any kicks (which we refer to as "after performing $0$ kicks"), after performing $1$ kick, $\ldots$, and after performing $d$ kicks,
and the set of reachable cells from his initial cell by repeating moves to a road without a kick enlarges (weakly) monotonically.
In particular, every cell passed through during his actions is reachable after performing $d$ kicks.
Then, for each cell passed through, we can assign an integer between $0$ and $d$ (inclusive) so that:
- If that cell is reachable before performing (any) kicks, assign $0$.
- If that cell is unreachable after performing $(i-1)$ kicks but is reachable after performing $i$ kicks, assign $i$.
Otherwise, if we consider a sequence $A=(A_1,A_2\ldots,A_{\lvert A\rvert})$ consisting of the numbers assigned to the cells passed through during the actions (allowing repeated occurrences), its final term is $d$ because it is the number assigned to cell $T$.
Since $0$ $(\neq d)$ is assigned to its first term, there exists $m$ such that $A_{\lvert A\rvert}=A_{\lvert A\rvert-1}=\cdots=A_{\lvert A\rvert-m+1}=d$ and $A_{\lvert A\rvert-m} < d$.
Here, by definition, a cell satisfies $A_i=d$ is either a cell that has become a road by the $d$-th kick or a cell that was initially a road, but if the $\left( \lvert A\rvert-m+1 \right)$-th visited cell was initially a road, then $A_{\lvert A\rvert-m}\geq A_{\lvert A\rvert-m+1}$, so it is a cell that has become a road by the $d$-th kick.
Hence, there is at least one cell that has become a road by the $d$-th kick among the $\left( \lvert A\rvert-m+1 \right)$-th, $\left( \lvert A\rvert-m+2 \right)$-th, $\ldots$、and $\lvert A\rvert$-th cells. Let $T'$ be the such cell that was visited for the last time (with the maximum index). The cell where the $d$-th kick (which we denote by cell $S'$) itself can be reachable after performing $(d-1)$ kicks, so one can construct a path of distance $(d-1)$ to the corresponding vertex. Since cell $T'$ has been turned into a road performed from cell $S'$, there is an edge of weight $1$ from the vertex corresponding to cell $S'$ to the vertex for $T'$.
In the course from cell $T$ to $T'$, all cells (but cell $T'$ itself) is a cell that was initially a road, so it is reachable from the vertex corresponding to cell $T'$ to the cell vertex for $T$ by traversing only weight-$0$ edges. Therefore, by concatenating a path from the vertex corresponding to his initial vertex to the vertex for cell $S'$ (which exists by assumption of the induction), the edge from the vertex for cell $S'$ to the vertex for cell $T'$, and the path of distance $0$ from the vertex for cell $T'$ to the vertex for cell $T$, we can construct a path of distance at most $d$.
Therefore, the proposition is proven true for $k=d$ too.
By the proof above, it has been shown that (the required number of kicks) \(\leq\) (the shortest path in \(G\)) and (the required number of kicks) \(\geq\) (the shortest path in \(G\)), which turn out to be equal. The shortest distance problem on the graph above can be solved with an algorithm like Dijkstra’s algorithm with appropriate implementation within the time limit, but this time, the edge weight is either \(0\) or \(1\), so we can conduct a 01-BFS (Breadth-First Search) to speed it up. 01-BFS is basically equivalent to Dijkstra’s algorithm, except that we use a deque instead of a priority queue by exploiting the property that tentative distances of vertices that are inserted to the deque differ at most by one, enabling us to solving the original problem in a total of \(O(HW)\) time. See also the official editorial of ABC246-E for more details on 01-BFS.
Hence, the construction of the graph \(G\) and computing the shortest distance can be both done in \(O(HW)\) time, which is fast enough.
Therefore, the problem has been solved.
Sample code in C++:
#include <bits/stdc++.h>
using namespace std;
int main() {
int h,w;
int a,b,c,d;
int x,y,z,nx,ny;
bool wall;
deque<int>dq;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
cin>>h>>w;
vector<string>s(h);
vector<vector<int> >ans(h,vector<int>(w,h*w));
for(int i=0;i<h;i++)cin>>s[i];
cin>>a>>b>>c>>d;
a--,b--,c--,d--;
ans[a][b]=0;
dq.push_front(a*w+b);
while(!dq.empty()){
z=dq.front();
dq.pop_front();
if(z==(c*w+d)){
cout<<ans[c][d]<<endl;
return 0;
}
x=z/w,y=z%w;
for(int i=0;i<4;i++){
wall=false;
for(int j=1;j<=2;j++){
nx=x+dx[i]*j;
ny=y+dy[i]*j;
if((nx<0)||(nx>=h)||(ny<0)||(ny>=w))break;
if(s[nx][ny]=='#')wall=true;
if(!wall){
if(j==1){
if(ans[nx][ny]>ans[x][y]){
ans[nx][ny]=ans[x][y];
dq.push_front(nx*w+ny);
}
}
}
else{
if(ans[nx][ny]>ans[x][y]+1){
ans[nx][ny]=ans[x][y]+1;
dq.push_back(nx*w+ny);
}
}
}
}
}
return 0;
}
投稿日時:
最終更新: