You are not logged in. Please login at www.codechef.com to post your questions!

×

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;
}

asked 04 Dec '14, 23:41

swagatochatt's gravatar image

0★swagatochatt
1536
accept rate: 0%

edited 05 Dec '14, 12:23


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

link

answered 04 Dec '14, 23:59

superty's gravatar image

3★superty
36417
accept rate: 31%

edited 05 Dec '14, 00:00

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.

(05 Dec '14, 12:24) swagatochatt0★
(05 Dec '14, 19:15) superty3★

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

(05 Dec '14, 19:31) swagatochatt0★

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

link

answered 11 Nov '15, 12:29

archit129's gravatar image

1★archit129
9239
accept rate: 0%

edited 11 Nov '15, 12:31

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,220
×734
×428
×400
×247
×37
×24

question asked: 04 Dec '14, 23:41

question was seen: 3,043 times

last updated: 11 Nov '15, 12:31