|
|
вернуться в форумWhy i got "WA"? help plz Послано Inside 27 июл 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; } |
|
|