Official

D - Grid and Magnet Editorial by en_translator


First, for a square \(S\) without a magnet, let us consider how to find its degree of freedom.
This can be found by BFS (Breadth-First Search) on a grid graph.
Consider a graph whose vertices are the squares without a magnet (let us call the vertex corresponding to a square \(A\) simply vertex \(A\)), and where there is an edge pointing from vertex \(A\) to vertex \(B\) if and only if one can make a move from square \(A\) to square \(B\). Then, the vertices reachable from vertex \(S\) via edges can be enumerated with DFS (Depth-First Search) and counted. (BFS also works.) The answers can be obtained by performing it for all squares (without a magnet).

However, since the graph has at most \(\Theta(HW)\) vertices and edges, finding the degree of freedom of one square costs \(\Theta(HW)\), for a total complexity of \(\Theta(H^2W^2)\) at worst, which is difficult to meet the time limit.

Now, notice that if one can reach from square \(A\) to square \(B\), ad no square adjacent to square \(B\) has a magnet, then the degree of freedom of square \(A\) and square \(B\) are the same. This is because, if there is no square adjacent to square \(B\) with a magnet, one can follow the reverse path from square \(A\) to square \(B\) to reach from square \(B\) to square \(A\), and thus every square \(C\) is reachable from \(A\) if and only if it is reachable from square \(B\). Therefore, if you find a square \(S'\) reachable while enumerating squares reachable from a square \(S\) and square \(S'\) does not have a magnet, you do not have to start over from square \(S'\). This can be managed by maintaining a flag for each square that indicates whether the square is already explored at least once.

We consider the complexity of this algorithm. Since the number of edges from each vertex is constant, the complexity is basically proportional to the number of pairs (starting square, another square reachable from it) that appear in the search.
Paying attention to the latter, we consider how many times each square appears as “a square reachable from somewhere.” Any square not adjacent to a magnet appears exactly once; if \(T\) appeared twice or more, it means \(T\) had been found to be reachable from two different squares \(S\) and \(S'\), but then one could reach from \(S\) via \(T\) to \(S'\) (and from \(S'\) to \(S\) too), which means that one did not have to start searching from both \(S\) and \(S'\). Conversely, even if the square is unreachable for any other squares, we have to count the number of squares reachable from itself, so it appears at least once.
A square \(T'\) adjacent to a magnet appears at most four times. Excluding the case where \(T'\) itself is the starting point, it always appear as a result of a move from another square. However, this previous square is not adjacent to a magnet (because he can make a move to \(T'\)), which appears only once in the search. Therefore, since \(T'\) has at most four adjacent squares, of which at least one has a magnet, a move into \(T'\) occur at most three times. Including the case where the starting point is \(T'\) itself, it appears at most four times.
Hence, there are at most \(O(HW)\) pairs (starting square, another square reachable from it), which allows us to solve the problem in a total of \(O(HW)\) time; this is fast enough.
Thus this problem has been solved.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

vector<int>e[1000000];
int used[1000000];
int cnt;

void dfs(int s,int v){
	if(used[v]==s)return;
	used[v]=s;
	cnt++;
	int sz=e[v].size();
	for(int i=0;i<sz;i++)dfs(s,e[v][i]);
	return;
}

int main(void){
	int dx[4]={0,0,1,-1};
	int dy[4]={1,-1,0,0};
	int h,w,ans=0;
	bool can;
	cin>>h>>w;
	vector<string>s(h);
	for(int i=0;i<h;i++)cin>>s[i];
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(s[i][j]=='#')continue;
			can=true;
			for(int k=0;k<4;k++){
				if((i+dx[k]>=0)&&(i+dx[k]<h)&&(j+dy[k]>=0)&&(j+dy[k]<w)){
					e[i*w+j].push_back((i+dx[k])*w+(j+dy[k]));
					if(s[i+dx[k]][j+dy[k]]=='#')can=false;
				}
			}
			if(!can){
				e[i*w+j].clear();
				continue;
			}
		}
	}
	for(int i=0;i<(h*w);i++)used[i]=-1;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if((s[i][j]=='.')&&(used[i*w+j]<0)){
				cnt=0;
				dfs(i*w+j,i*w+j);
				ans=max(ans,cnt);
			}
		}
	}
	cout<<ans<<endl;
}

posted:
last update: