My code works the same as you say:
"
The result should be 0 like this:
3 3 3 2 2
3 4 3 3 2
3 3 4 3 3
2 3 3 4 3
2 2 3 3 3
"
all test fine but after submit 2test falls.
i have no idea, my solution is using sqrt((x1-x2)²+(y1-y2)²)
05 THEY have a medium cellar
06 THEY have a large cellar
You should use the Manhattan distance, not the euclidean distance.
I pass all the test cases which privided in IDE,but when I submit my code,it shows fail in 06 THEY have a large cellar.
I can’t find which mistake I made in my code,could anyone help me here?
Here’s my code.
<?php
function searchArray($array,$target){
if(!empty($array)){
foreach($array as $k0 => $v0){
foreach($v0 as $k1 => $v1){
if($v1 == $target){
$return[] = "{$k0},{$k1}";
}
}
}
if(isset($return)){
return $return;
}
return false;
}
}
function printBrightnessMap(){
global $brightness;
for($i = 0;$i < count($brightness);$i++){
for($ii = 0;$ii < count($brightness[$i]);$ii++){
echo $brightness[$i][$ii]." ";
}
echo PHP_EOL;
}
}
fscanf(STDIN, "%d", $N);//height & width
fscanf(STDIN, "%d", $L);//default light level
for($i = 0; $i < $N; $i++){
$LINE = stream_get_line(STDIN, 500 + 1, "\n");
$matrix[] = explode(" ",$LINE);
}
//init brightness
$brightness = array_fill(0,$N,0);
for($i = 0;$i < count($brightness);$i++){
$brightness[$i] = array_fill(0,$N,0);
}
$light = searchArray($matrix,"C");
if($light !== FALSE){
foreach($light as $k => $v){
$position = explode(",",$v);
//print_r($position);
$x = $position[0];
$y = $position[1];
$brightness[$x][$y] = $brightness[$x][$y] + $L;
for($i = 1;$i < $L;$i++){
$bright = $L - $i;
if($x - $i >= 0){
$brightness[$x - $i][$y] = $brightness[$x - $i][$y] + $bright;
}
if($x + $i < $N){
$brightness[$x + $i][$y] = $brightness[$x + $i][$y] + $bright;
}
if($y - $i >= 0){
$brightness[$x][$y - $i] = $brightness[$x][$y - $i] + $bright;
}
if($y + $i < $N){
$brightness[$x][$y + $i] = $brightness[$x][$y + $i] + $bright;
}
if($x - $i >= 0 && $y - $i >= 0){
$brightness[$x - $i][$y - $i] = $brightness[$x - $i][$y - $i] + $bright;
if(isset($brightness[$x - $i - 1][$y - $i]) && $bright != 1){
$brightness[$x - $i - 1][$y - $i] = $brightness[$x - $i - 1][$y - $i] + $bright - 1;
}
if(isset($brightness[$x - $i][$y - $i - 1]) && $bright != 1){
$brightness[$x - $i][$y - $i - 1] = $brightness[$x - $i][$y - $i - 1] + $bright - 1;
}
}
if($x - $i >= 0 && $y + $i < $N){
$brightness[$x - $i][$y + $i] = $brightness[$x - $i][$y + $i] + $bright;
if(isset($brightness[$x - $i - 1][$y + $i]) && $bright != 1){
$brightness[$x - $i - 1][$y + $i] = $brightness[$x - $i - 1][$y + $i] + $bright - 1;
}
if(isset($brightness[$x - $i][$y + $i + 1]) && $bright != 1){
$brightness[$x - $i][$y + $i + 1] = $brightness[$x - $i][$y + $i + 1] + $bright - 1;
}
}
if($x + $i < $N && $y - $i >= 0){
$brightness[$x + $i][$y - $i] = $brightness[$x + $i][$y - $i] + $bright;
if(isset($brightness[$x + $i + 1][$y - $i]) && $bright != 1){
$brightness[$x + $i + 1][$y - $i] = $brightness[$x + $i + 1][$y - $i] + $bright - 1;
}
if(isset($brightness[$x + $i][$y - $i - 1]) && $bright != 1){
$brightness[$x + $i][$y - $i - 1] = $brightness[$x + $i][$y - $i - 1] + $bright - 1;
}
}
if($x + $i < $N && $y + $i < $N){
$brightness[$x + $i][$y + $i] = $brightness[$x + $i][$y + $i] + $bright;
if(isset($brightness[$x + $i + 1][$y + $i]) && $bright != 1){
$brightness[$x + $i + 1][$y + $i] = $brightness[$x + $i + 1][$y + $i] + $bright - 1;
}
if(isset($brightness[$x + $i][$y + $i + 1]) && $bright != 1){
$brightness[$x + $i][$y + $i + 1] = $brightness[$x + $i][$y + $i + 1] + $bright - 1;
}
}
}
}
//printBrightnessMap();
$darkBlocks = searchArray($brightness,0);
if($darkBlocks !== FALSE){
echo count($darkBlocks);
}else{
echo 0;
}
}else{
echo count(searchArray($brightness,0));
}
?>
Manhattan distance gives a diamond shape to light propagation. The statement explains light propagate in a square shape, so it’s clearly not Manhattan distance.
However, looking at the way Manhattan distance is calculated can help, but trying to implement it as is will fail.
I think that the explanations and the tools given could be improved.
First, it is useless to separate each character by a space in the input. It makes things confusing and harder for no purpose. In particular, the size of the input grid is not nn but n2n, which does not match other problems.
Second, the decay feature is useless. For each candle, one can simply explore a square around it and mark each visited box, without caring about the amount of light.
Third, the output should be the complete grid. Then, it would make sense with what is given.
I guess it is a bit late to modify it now…
1 Like
It is possible to solve it with just some conditions.
Hi,
As many my code did well in the IDE tests but failed on submission on tests 5 and 6.
I did my code in C#.
How can i know the cause of failure? It was by timeout or something else?
Can i send to anyone in order to help me?
Thanks
Me too, fail on No 5.
Validator 5 is almost the same as the Testcase no. 5. Only the parameter in the second line is 5 instead of 3 and the solution is 0 instead of 14.
If you want test your program with a testcase created on your own you can look at this post: https://www.codingame.com/forum/t/community-puzzle-rectangle-partition/126826/96
1 Like
That was fun!
Hey there!
Only 88% after hours of thinking… 
Didn’t pass validator 6, what could be wrong ? I know my light brightnesses are not good everywhere but I don’t think it matters for this issue. Is it possible to get the input of this validator ?
Here you go:
INPUT
20
4
X X X C X C X X X X X X X X X X X X X X
X C X X X C X X X X C X X X X C X X X X
X X X X X X X X X X X X X C C X X X X X
X X X X X X X X X X X X X X X X X X X X
X X X X X X X X X X X X X X X X X X X C
X X X X X X X X C X X X X X X X C X X X
X X X X X C X X X X X X X X C X X X X C
X X X X X X C X X C C C X X X X X X X X
X C X X X X X X X X C X X X C X X X X X
X X X X C X X C X X X X X X X X X C X X
X X X X X X X X X C X C X X X X X X X X
X X X X X X X X X X X X X X X X X X X X
X X X X X X C X X X X X X X X X X C X X
X X X X X X X X X X X X X X X X X X X X
X X X X X X X X X C C X X X X C X X X X
X X X X X X X X X X X X C C C X X X X X
X X X X X X X X C X X X X X X X C C X X
X X X C X X X X X X X X X X X X X C X X
X X X X X C X X X X X X X X X C X X X X
X C X C X X X X X X X X X X X X X X X X
OUTPUT
5
Thank you ! It helped me to see that my calculations were wrong. Finally I decided not to take care about the brightness and I rewrote my code differently (and waaaaaaay simplier) and everything works.
1 Like
Wow! Thank you
Damn I was mindblown when I saw some of the top solutions on several lines of code. Great puzzle! Nice learning experience for a newbie!
1 Like
Same for me, test 05 and 06 fail.
For test 05, result should be: 14 but if I count manually, I count 16 cells without light.
The cells in rows 9 and 10 in your figure should be lighted (you missed one “3” in cell F8).
2 Likes
My bad. I understand my mistake finally… Thank you !
1 Like
Kinda fun puzzle, i used range from left-right and up-down to set canlde light.
It would be harder if i need to display array with candle range displayed.
Used some if statements, later i want to fix with better algorithm
I really had fun working on this, Thank You!