ZCO problem Little Red Riding Hood

dfs
dynamic-programming
inoi
ioi
zco
zco2015

#1

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*[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*[j])? printf("1 "):printf("0 ");
    }
    printf("

");
}/
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
[0] = (w*[0])? (tc[i-1][0] + map[0]*):-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*[j]){
            tc*[j]=-99999;
            continue;
        }
         else{
            tc*[j]=max(tc*[j-1],tc[i-1][j]);
            tc*[j]+=(tc*[j]==-99999)?0:map*[j];
         }
    }
}
(tc[n-1][n-1]==-99999)? printf("NO"):printf("YES

%d",tc[n-1][n-1]);
return 0;
}


#2

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


#3

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


#4

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.


#5

http://pastebin.com/CuQqK8ZJ


#6

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