The labyrinthitis is a serious problem* which effect many people, is particularly common in people between the age of 18 to 99 owning a driving license and a car, you may encounter on the road on a daily basis people with this illness! Drive safe out there!
If you are confused, well I understand!I’m trying to make fun here of an Italian way of talking about people which lost themselves everywhere or that are not able to decide whether to turn right or left but by trial, this is particularly true between car driver which almost kill everybody on the road by fast lane changes &c: “P.D.! ma che cazzo c’hai la labirintite?” How many time I was yelling in this way on the highway…
Furthermore the labyrinthitis is a real illness which have nothing to do with labyrinths, but the name of the sickness sound very familiar to to the word labyrinth, which in turn looks like as you’re talking about someone with a Labyrinth problem 🙂 –How funny those computer nerds are huh?–
Before going ahead with the problem I want to discuss with this post, I need you to be sure about what is a graph, how a DFS works and what a connected component is. If you have any doubt then find some reference on the web and then come back, I will try to explain some minor details here anyway.
Assume that you’re given a matrix MxN where 0<=i<=M, 0<=j<=N, and that A[i,j] may be ‘*’ or ‘.’, like:
4 5 **..* ..*** ..*.. *.*..
If we consider each ‘*’ as an impassable obstacle and dot’s as cells one is allowed to traverse, then we may consider that matrix a labyrinth! –Ignore please the little missing detail of not having specified the entrance and the exit of the maze, we are not going to path a way out of a labyrinth here.–
In this “labyrinth” we are allowed to move from one cell to another in four possible directions: up,down,left and right. If, of course, the target cell is not an obstacle!
For the example matrix we have here, the graph looks like this way:
The dots can be connected together in order to build the graph, as you can see from the example I’m not able to build a connected graph and therefore I have some connected components, in this case three.
That’s unfortunate, since if happen that a poor bastard jumps in one the connected components and his girlfriend in a different one, well, they’re not going to meet very soon.. –Thanks God he have a wireless connection and a browser!–
In order to calculate the number of connected components in a graph you may use a pretty straightforward approach which exploit the DFS capability of tracking the vertex already visited, basically you run in a loop the DFS algorithm till no more not-visited vertex are available, the amount of time DFS ran accounts the number of connected components.
DFS and any of the available graph traversal algorithms are going to visit all the vertex reachable from the source via a simple path, so if a given vertex is not reachable it must be in a different connected component of the graph.
Using this approach you may calculate the amount of vertex in each connected component, and this last calculation brings us straight to the problem I want to solve today!
For each of the impassable cells, you’re asked to calculate the size of the connected component resulting from changing the given cell from impassable to passable.
Once calculated all those sizes, print out a matrix where each impassable cell is substituted by the size of the relative connected component modulo 10, and the free cells are marked with ‘.’ as for the input matrix.
So each time we have an impassable cell, we change it to passable and run DFS to calculate the size of the connected component resulting from this modification, applying this algorithm on our example input matrix, we get:
68..3 ..875 ..0.. 6.0..
But running DFS each and every time is going to be very slow, and most connected components are going to be traversed multiple times, once for each impassable cell changed to passable! Too slow, let’s think about a possible optimization.
What if each component size is calculated once, and that size is saved for further usage? This sound clever, we can mark each cell of a given connected component with an unique number and map this number with the correct size.
Then the algorithm would be:
- For each impassable cell check if any of the adjacent cells have a valid mark
- For each valid mark, sum the relative connected component size and add one.
- substitute the impassable cell symbol ‘*’ with the size modulo 10.
Since we are substituting each ‘*’ with a number modulo ten, we must avoid the situation where an already computed cell is mistaken with a mark of a connected component, for this reason the marks should be negative. For clarity purpose, we should also substitute every ‘*’ with the number 0.
Connected components (‘,’ added for clarity)
0,0,-1,-1,0
-2,-2,0,0,0
-2,-2,0,-3,-3
0,-2,0,-3,-3mapping:
mark: -1 size: 2
mark: -2 size: 5
mark: -3 size: 4
And now we are done, each 0 is an impassable cell for which we need to calculate the connected component size and write in that cell the result modulo 10, this is the resulting code:
//http://codeforces.com/problemset/problem/616/C
#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
long labyrinth[1001][1001];
map<long,long> conn_comp_size;
int mark{-1};
int n,w;
int used_marks[4];
int marks_i{0};
long dfs(int x,int y)
{
if(labyrinth[y][x]<=0) return 0;
++conn_comp_size[-mark];
long r{1};
labyrinth[y][x] = mark;
if(x-1>=0) r+=dfs(x-1,y);
if(x+1<w) r+=dfs(x+1,y);
if(y-1>=0) r+=dfs(x,y-1);
if(y+1<n) r+=dfs(x,y+1);
return r;
}
bool try_to_mark(int pattern)
{
if(pattern==0) return false;
for(int i{0};i<marks_i;i++)
if(used_marks[i]==pattern)
return false;
used_marks[marks_i++] = pattern;
return true;
}
int main()
{
std::ios::sync_with_stdio(false);
cin >> n >> w;
string s;
for(int i{0};i<n;i++)
{
cin >> s;
for(int j{0};j<w;j++)
{
labyrinth[i][j] = (s[j] == '.') ? 1 : 0;
}
}
//Mark each connected component size:
for(int i{0};i<n;i++)
{
for(int j{0};j<w;j++)
{
if(labyrinth[i][j]>0)
{
dfs(j,i);
--mark;
}
}
}
//Solve the problem:
for(int i{0};i<n;i++)
{
for(int j{0};j<w;j++)
{
if(labyrinth[i][j]==0)
{
long r{1};
if(j-1>=0){
if(try_to_mark(labyrinth[i][j-1]))
r+=conn_comp_size[-labyrinth[i][j-1]];
}
if(j+1<w){
if(try_to_mark(labyrinth[i][j+1]))
r+=conn_comp_size[-labyrinth[i][j+1]];
}
if(i-1>=0){
if(try_to_mark(labyrinth[i-1][j]))
r+=conn_comp_size[-labyrinth[i-1][j]];
}
if(i+1<n){
if(try_to_mark(labyrinth[i+1][j]))
r+=conn_comp_size[-labyrinth[i+1][j]];
}
cout<<r%10;
//Clear the marks
marks_i = 0;
used_marks[0] = used_marks[1] = 0;
used_marks[2] = used_marks[3] = 0;
}
else cout<<'.';
}
cout<<endl;
}
}
The function try_to_mark may need a little more explanation, it basically check if the selected adjacent cell has a valid mark (!=0) and if his mark was not already used to sum up the current component size:
-1,-1,-1 -1,0,-1 -1,-1,-1
In the example above there’s only one connected component and one impassable cell, once we’re on that impassable cell and the code checks for adjacent cells then he’ll find a cell in each direction –up,down &c-, but each time the connected component is the same and we don’t want to use its size more than once, for this reason the code check whether a given mark was already used or not –used_marks array-.
Thanks for reading!