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