Source Code

Problem: 1124  User: yzhw 
Memory: 708K  Time: 16MS 
Language: G++  Result: Accepted 

Source Code 
#include <iostream>
# include <cstdio>
# include <vector>
# include <queue>
# include <cstring>
using namespace std;
char map[25][25];
double num[1000];
int w,h;
int cal(int e,int pos,vector<int> refer[])
{
     if(pos==e) return 1;
     else
     {
      
         int total=0;
         for(int i=0;i<refer[pos].size();i++)
           total+=cal(e,refer[pos][i],refer);
         return total;
     }
     
}
void dfs(int e,int pos,vector<int> refer[],int l[],int level,double load)
{
     if(pos==e)
     {
        for(int i=2;i<level;i++)
          num[l[i]]+=load;
        return;
     }
     else
     {
         l[level]=pos;
         for(int i=0;i<refer[pos].size();i++)
            dfs(e,refer[pos][i],refer,l,level+1,load);
     }
}
void bfs(int s,int e,vector<int> refer[])
{
     int len[1000];
     bool used[1000];
     memset(len,0,sizeof(len));
     memset(used,0,sizeof(used));
     queue<int> q;
     q.push(s);
     used[s]=1;
     while(!q.empty())
     {
       int pos=q.front();
       q.pop();
       if(pos==e) break;
       if(pos/w&&map[(pos-w)/w][(pos-w)%w]=='.')//up
       {
          if(!used[pos-w])
          {
             used[pos-w]=1;
             len[pos-w]=len[pos]+1;
             refer[pos-w].push_back(pos);
             q.push(pos-w);
          }
          else if(len[pos-w]==len[pos]+1)
             refer[pos-w].push_back(pos);
       }
       if(pos/w!=h-1&&map[(pos+w)/w][(pos+w)%w]=='.')//down
       {
          if(!used[pos+w])
          {
             used[pos+w]=1;
             len[pos+w]=len[pos]+1;
             refer[pos+w].push_back(pos);
             q.push(pos+w);
          }
          else if(len[pos+w]==len[pos]+1)
             refer[pos+w].push_back(pos);
       }
       if(pos%w&&map[(pos-1)/w][(pos-1)%w]=='.')//left
       {
          if(!used[pos-1])
          {
             used[pos-1]=1;
             len[pos-1]=len[pos]+1;
             refer[pos-1].push_back(pos);
             q.push(pos-1);
          }
          else if(len[pos-1]==len[pos]+1)
             refer[pos-1].push_back(pos);
       }
       if(pos%w!=w-1&&map[(pos+1)/w][(pos+1)%w]=='.')//right
       {
          if(!used[pos+1])
          {
             used[pos+1]=1;
             len[pos+1]=len[pos]+1;
             refer[pos+1].push_back(pos);
             q.push(pos+1);
          }
          else if(len[pos+1]==len[pos]+1)
             refer[pos+1].push_back(pos);
       }
     }
}
void solve(char s,char e,int l)
{
     int x1,y1,x2,y2;
     vector<int> refer[1000];
     int li[1000];
     for(int i=0;i<h;i++)
       for(int j=0;j<w;j++)
         if(map[i][j]==s)
           x1=i,y1=j;
         else if(map[i][j]==e)
           x2=i,y2=j;
     map[x2][y2]='.';
     bfs(x1*w+y1,x2*w+y2,refer);
     int divide=cal(x1*w+y1,x2*w+y2,refer);
     dfs(x1*w+y1,x2*w+y2,refer,li,1,(double)l/divide);
     map[x2][y2]=e;
}
int main()
{
    memset(num,0,sizeof(num));
    scanf("%d %d",&w,&h);
    for(int i=0;i<h;i++)
      scanf("%s",map[i]);
    char tmp[5];
    while(1)
    {
       int load;
       scanf("%s %d",tmp,&load);
       if(!strcmp(tmp,"XX")) break;
       solve(tmp[0],tmp[1],load);
    }
    for(int i=0;i<w*h;i++)
    {
        printf("%7.2f",num[i]);
        if(i%w==w-1) printf("\n");
    }
  // system("pause");
    return 0;
}