# ZCO problem Little Red Riding Hood

I am trying to solve this problem(http://www.iarcs.org.in/inoi/2013/zco2013/zco2013-1b.php)
This is the code I wrote.I have no idea why this is being given a TLE. Can this be improved ?

Maximum cost path is definitely an O(n^2+2n) algorithm. Is floodfill the cause of all trouble?

The Code:

#include <cstdio>
#include <algorithm>
using namespace std;
int map[500][500],tc[500][500];
bool w[500][500]{{false}};
int n,m,a,b,c;
void ffill(int r,int c,int l,int k){
if(!w[r][c]){
w[r][c]=true;
if(k<l){
if(r > 0) ffill(r-1,c,l,k+1);
if(r < n-1) ffill(r+1,c,l,k+1);
if(c > 0) ffill(r,c-1,l,k+1);
if(c < n-1) ffill(r,c+1,l,k+1);
}
}
}//A basic flood fill algorithm

int main(){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&map[i][j]);
}
}
for(int i=0;i<m;i++){
scanf("%d %d %d",&a,&b,&c);
ffill(a-1,b-1,c,0);
}
/*for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
(w[i][j])? printf("1 "):printf("0 ");
}
printf("\n");
}*/
if(!w[0][0]||!w[n-1][n-1]){printf("NO");return 0;}
tc[0][0]=map[0][0];
for(int i=1;i<n;i++){
//if(!w[i-1][0]) continue;
tc[i][0] = (w[i][0])? (tc[i-1][0] + map[0][i]):-99999;
}
for(int j=1;j<n;j++){
//if(!w[0][j-1]) continue;
tc[0][j] = (w[0][j])? (tc[0][j-1] + map[0][j]):-99999;
}

for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if (!w[i][j]){
tc[i][j]=-99999;
continue;
}
else{
tc[i][j]=max(tc[i][j-1],tc[i-1][j]);
tc[i][j]+=(tc[i][j]==-99999)?0:map[i][j];
}
}
}
(tc[n-1][n-1]==-99999)? printf("NO"):printf("YES\n%d",tc[n-1][n-1]);
return 0;
}

You don’t seem to be checking if a square has already been visited in your flood fill.

I’ve added the condition for preventing re-evaluation of a square twice(the in the code there in my question),yet still for some test cases the server is marking me WA.Please help.

Can you point out what’s the problem in this new code that I’ve written according to your suggestion

Can anyone tell what’s wrong with my solution? - http://pastebin.com/VRPVbAW0

I didnt have enough points to ask a new question myself and the olympiad is approaching fast

It fails on tasks 1, 3 and 7

1 Like
//