I used BFS and getting WA#4 but I don't know why my BFS doesen't get AC!
This is my code:


#include<bits/stdc++.h>
using namespace std;
#define X saf[0].first+dir[d][0]
#define Y saf[0].second+dir[d][1]
#define F first
#define S second
#define mp make_pair
const int M=1002;
int dir[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
deque<pair<int,int> >saf;
pair<int,int> mark[M][M],ans,l[M];
char land[M][M];
int n,m,k;
double v;
int inland(int x,int y)
{
    if(x<1 || x>n || y<1 || y>m)
        return false;
    return true;
}
void bfs(int h)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            mark[i][j].F=mark[i][j].S=0;
    saf.clear();
    saf.push_back(mp(l[h].F,l[h].S));
    mark[l[h].F][l[h].S]=mp(1,0);
    while(saf.size())
    {
        for(int d=0;d<8;d++)
            if(inland(X,Y))
            if(!mark[X][Y].F && !mark[X][Y].S && land[X][Y]=='.')
            {
                mark[X][Y]=mark[saf[0].F][saf[0].S];
                if(d>3)
                    mark[X][Y].S++;
                else
                    mark[X][Y].F++;
                saf.push_back(mp(X,Y));
            }
        saf.pop_front();
    }
}
int main()
{
    cin>>m>>n>>k>>v;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>land[i][j];//scanf("%c",&land[i][j]);
    for(int i=0;i<=k;i++)
        scanf("%d%d",&l[i].second,&l[i].first);
    for(int i=0;i<k;i++)
    {
        bfs(i);
        if(!mark[l[i+1].F][l[i+1].S].F && !mark[l[i+1].F][l[i+1].S].S)
        {
            l[i+1]=l[i];
            continue;
        }
        ans.F+=mark[l[i+1].F][l[i+1].S].F-1;
        ans.S+=mark[l[i+1].F][l[i+1].S].S;
    }
    double x=(double)ans.F+(double)ans.S*sqrt(2.0);
    printf("%.21f",x/v);
    return 0;
}

Edited by author 11.09.2016 17:51

BFS is okay, i use BFS in my solution. The thing is, it's not that simple as it usually is, in fact~
Here's an example for you:
5 8 1 1.00
.....
.....
.#...
.##..
.###.
.##..
.#...
.....
1 1
3 8
If we move down, we do 6 vertical + 1 diagonal + 1 horizontal = 8 jumps with distance 8.41.
But, if we move diagonally, we do 4 diagonal jumps right, 2 diagonal jumps left and 1 vertical = 7 jumps, but greater distance (your program says 9.48).
So take into account that less "jumps" is not always less distance.
If you redo your BFS properly, it should work out.
Good luck!