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