|  | 
|  | 
| back to board | Why i got "WA"? help plz Posted by Inside  27 Jul 2007 23:33#include <iostream>#include <vector>
 #include <queue>
 #include <cstdio>
 
 using namespace std;
 
 char A[75][75];
 int B[5625][9];
 int color[5625];
 double d[5625];
 int n,m;
 queue<short> q;
 const double dva = 1.4142135623730950488016887242097;
 void BFS(int s)
 {
 int i,u;
 for(i=0;i<n*m;i++)
 {
 color[i]=0;
 d[i]=-1.0;
 }
 color[s]=1;
 d[s]=0.0;
 q.push(s);
 while (!q.empty())
 {
 u=q.front();
 for(i=0;i<8;i++)
 {
 if(B[u][i]==-1) break;
 if(color[B[u][i]]==0)
 {
 color[B[u][i]]=1;
 if(B[u][i]==(u-1) || B[u][i]==(u+1) || B[u][i]==(u-n) || B[u][i]==(u+n))
 d[B[u][i]]=d[u]+1.0;
 else d[B[u][i]]=d[u]+dva;
 q.push(B[u][i]);
 }
 }
 q.pop();
 color[u]=2;
 }
 }
 int main()
 {
 int k,i,j,x,y,s,f,u,z,c;
 double dist=0.0,v;
 cin>>n>>m>>k>>v;
 for(i=0;i<m;i++)
 for(j=0;j<n;j++)
 cin>>A[i][j];
 for(i=0;i<n*m;i++)
 {
 j=0;u=i;
 if((u+n)<(n*m) && A[(u+n)/n][(u+n)%n]!='#') {B[i][j]=(u+n);j++;}
 if((u-n)>-1 && A[(u-n)/n][(u-n)%n]!='#') {B[i][j]=(u-n);j++;}
 if((u+1)%n!=0 && A[(u+1)/n][(u+1)%n]!='#') {B[i][j]=(u+1);j++;}
 if(u%n!=0 && A[(u-1)/n][(u-1)%n]!='#') {B[i][j]=(u-1);j++;}
 if((u-n-1)>-1 && (u-n)%n!=0 && A[(u-n-1)/n][(u-n-1)%n]!='#'){B[i][j]=(u-n-1);j++;}
 if((u-n+1)>-1 && (u-n+1)%n!=0 && A[(u-n+1)/n][(u-n+1)%n]!='#'){B[i][j]=(u-n+1);j++;}
 if((u+n-1)<(n*m) && (u+n)%n!=0 && A[(u+n-1)/n][(u+n-1)%n]!='#'){B[i][j]=(u+n-1);j++;}
 if((u+n+1)<(n*m) && (u+n+1)%n!=0 && A[(u+n+1)/n][(u+n+1)%n]!='#'){B[i][j]=(u+n+1);j++;}
 B[i][j]=-1;
 }
 cin>>y>>x;
 s=(x-1)*n+y-1;
 for(i=0;i<k;i++)
 {
 BFS(s);
 cin>>y>>x;
 f=(x-1)*n+y-1;
 if(d[f]==-1) continue;
 dist+=d[f];
 s=f;
 }
 printf("%.2lf\n",dist/v);
 return 0;
 }
 | 
 | 
|