ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1254. Крепкий орешек

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;
}