1321. Robot

  1 /*单源最短路径
  2  *日,因为把计算节点的算式写错了，错到死
  3  *节点太多，所以在转化成无向图的时候需要压缩一下
  4  *因为一个节点最多与4个节点相连接，所以只需要保存4个相邻节点的信息就可以了
  5  *
  6  *
  7  *
  8  *
  9  */
 10 
 11 
 12 #include <iostream>
 13 #include <memory.h>
 14 #include <vector>
 15 #define inf 10000000
 16 using namespace std;
 17 int rd[10010][4];//记录某一节点相连接节点的权
 18 int np[10010][4];//记录某一节点相连接节点的号码
 19 int n[10010];//记录某一节点相连接节点的数目
 20 int vl[110][110];
 21 int vi[10010];
 22 int ans[10010];
 23 int r,l;
 24 int a,b,c,d;
 25 void set()//转化成无向图
 26 {
 27         memset(n,0,sizeof(n));
 28         for(int i=1;i<=r;i++)
 29                 for(int j=1;j<=l;j++)
 30                 {
 31                         int tem=(i-1)*l+j;
 32         //             cout<<tem<<" ";
 33                         if(i+1<=r)
 34                         {
 35                                 rd[tem][n[tem]]=vl[i+1][j];
 36                                 np[tem][n[tem]]=tem+l;
 37                                 n[tem]++;
 38                         }
 39                         if(i-1>0)
 40                         {
 41                                 rd[tem][n[tem]]=vl[i-1][j];
 42                                 np[tem][n[tem]]=tem-l;
 43                                 n[tem]++;
 44                         }
 45                         if(j+1<=l)
 46                         {
 47                                 rd[tem][n[tem]]=vl[i][j+1];
 48                                 np[tem][n[tem]]=tem+1;
 49                                 n[tem]++;
 50                         }
 51                         if(j-1>0)
 52                         {
 53                                 rd[tem][n[tem]]=vl[i][j-1];
 54                                 np[tem][n[tem]]=tem-1;
 55                                 n[tem]++;
 56                         }
 57                 }
 58 }
 59 void sl()
 60 {
 61         int root=(a-1)*l+b;
 62         for(int i=1;i<=r*l;i++)
 63                 ans[i]=inf;
 64         for(int i=0;i<n[root];i++)
 65                 ans[np[root][i]]=rd[root][i];
 66         memset(vi,0,sizeof(vi));
 67         ans[root]=0;
 68         vi[root]=1;
 69         
 70         for(int i=2;i<=r*l;i++)
 71         {
 72                 int tmp=inf;
 73                 int u=-1;
 74                 for(int j=1;j<=r*l;j++)
 75                 {
 76                         if(!vi[j]&&ans[j]<tmp)
 77                         {
 78                                 u=j;
 79                                 tmp=ans[j];
 80                         }
 81                 }
 82                 vi[u]=1;
 83                 for(int j=0;j<n[u];j++)
 84                 {
 85                         if(!vi[np[u][j]])
 86                         {
 87                                 if(ans[u]+rd[u][j]<ans[np[u][j]])
 88                                         ans[np[u][j]]=ans[u]+rd[u][j];
 89                         }
 90                 }
 91 
 92         }
 93 }
 94 int main()
 95 {
 96         int t;
 97         cin>>t;
 98         while(t--)
 99         {
100         
101 
102                 cin>>r>>l;
103                 for(int i=1;i<=r;i++)
104                         for(int j=1;j<=l;j++)
105                                 cin>>vl[i][j];
106                 set();
107 
108                 cin>>a>>b>>c>>d;
109                 sl();
110 
111                 cout<<ans[(c-1)*l+d]+vl[a][b]<<endl;
112         }
113 }