### ILoveShreya's blog

By ILoveShreya, history, 8 months ago, ,

I am trying to solve a bfs problem. But i am getting WA.First I try to find what's the wrong in my code without taking any help,then i have used SPOJ Toolkit with the available test case to find mistake in my code.But i'm again fail :(

Of course there is a problem in my code that's why i am getting WA but i haven't found it. My code link: code link.

Help please to find out why i'm getting WA.

•  » » » 8 months ago, # ^ | ← Rev. 2 →   +1 yes, i checked your code, and i think there is one problem with the input, so i changed this and now is giving TLE :( codescanf("%d", &tt); while(tt--) { memset(vis,20,sizeof(vis)); memset(dis,20,sizeof(dis)); //printf("vis = %d\n",vis[56][78]); scanf("%d %d", &n, &m); for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { scanf("\n%c", &ch); if(ch=='S') { sx=i,sy=j; } if(ch=='F') { tx=i,ty=j; } str[i][j]=ch; } } if(n==1 && m==1){ printf("-1\n"); continue; } S.x=sx; S.y=sy; S.mov=0; S.dir=-1; F.x=tx; F.y=ty; printf("%d\n", bfs(S, F)); while(!qq.empty()) qq.pop_front(); }Another point is, the way you model the graph makes him one weighted graph, because the lines 45~52 shows that there is two weights for one edge 0 or 1. So i changed your code to a djikstra, and got TLE, after i tried to use the 0-1BFS, and got TLE too :( .I guess the solution is, for each time when you are in a position (row, col), and the direction that you go is i, you use the move (dx[i], dy[i]) until you catch one blocked cell, you need to enqueue all cell's (x, y) that's is not visited, another observation is if you find one cell (x, y) that's already is visited, and her distance dis[x][y] < dis[ros][col] + 1, you can stop too. This way you just need the array dis[row][col] to store the distances, and not dis[row][col][dir].