I m trying to up solve this problem… I I could think is calculate all the X values*4 and then find the adjacent using DFS to subtract. If you guys have something else… please tell me. Or if I m wrong, please help me. Thanks a lot
DFS/BFS would be apt.
Use BFS/DFS on tile from where you find X.
(keep them marked so that you don’t visit them)
The position of tile is important and it will be the multiplier that is needed
divide that into several cases.
if a tile is singly alone.
for example:
yyy
yxy
yyy
that will have multiplier of 4 for that tile.
if a tile has an x besides it’s one side
yyy
yxx
yyy
so the multiplier for the central x tile will be 3 and similarly for side x tile will be 3 as well.
There are more cases
This can be generalised as if we encounter an x tile. we will check for the number of x on all 4 sides,let’s name that a.
so the number to be multiplied will be:
4-a
1 Like
yyy
yxx
yyy
How only 2 for the right side?.. like… let’s take the 2nd tile… top, right,down… so it’s 3 right? How 2? Thanks for considering
right is in the corner right?
so we count that as open…
oh right i made a mistake ;_;
i am very sorry
1 Like
here is an example for 2
yyyy
yxyy
yxyy
yxyy
so the x in 3rd row will have 2 sides which are open
Chill… but to find the position of X’s… we use 2D array iteration?
you can do by that too
or use dfs/bfs
time complexity will be same for both
1 Like
I don’t think you need graph algorithms for this question.
It can be done by brute force.
Here is my brute force solution. It does fail on one test case, I have no idea why. Can someone tell me?
Ideone link if you want to see my code
can’t view your code.
Send IDEONE link…
And yeah i said so but it can be done with basic DFS and BFS it’s not necessary
2 Likes
Actually yes… brute can do it… since there is no constraints… we can just do the method… instead of visiting… we can check the immediate neighbors of X… is X has another X immediate to it… we add 0… else we add 1… we check all the possible sides of the X we choose… is this your approach?
My approach was to have two 2d boolean arrays that together correspond to all the edges of the floor. A true value means that the edge is a part of the perimeter. Then iterate through all the x’s and change the values in the 2d arrays accordingly. Then remove all the ‘true’ edges that lie between two x’s. And at last count the total number of x’s in the two arrays.
I am not sure if the approach is fully correct as it fails on one test case (It could be an implementation mistake though.)
Hey
Sorry for the late reply. Did you use DFS here?
nope normal traversal
1 Like
Recursive?
no it’s just a normal for loop
One personal question bro. How long did it take for you to get 3*?
not really long personally,
Solve two questions from cook off or lunch time quickly and you are in.
I am not sure about Long I don’t do them much often.
I focus more on short rounds and codeforces.
Where do you learn how to solve problems? Can you recommend something for poor like me 
Atcoder ABC, Codeforces Div 3, ZCO IARCS and INOI practise, codemonk hackerearth, hackerrank or CSES.fi XP
there are many more sites to practise like Timus,SPOJ,UVA,CSacademy and USACO which are very good.
But Atcoder ABC and Codeforces Div 3 are really good to implement basic knowledge.
Rest all you have to do is practise and practise while learning new concepts.
2 Likes