1 #include<iostream>  2 #include<stdio.h>  3 #include<string.h>  4 #include<stack>  5 #include<queue>  6 using namespace std;  7 #define maxx 44  8 #define maxx2 44*44  9 #define INF 99999999 10 char s[maxx][maxx]; 11 bool tong[maxx2][maxx2],vis[maxx2]; 12 int xing[maxx2],n,m,pre[maxx2],scc_num[maxx2],c,value[maxx2],low[maxx2],scc_count,scc_value[maxx2],d[maxx2]; 13 vector<int > g[maxx2],reg[maxx2]; 14 stack<int > sta; 15  16 void dfs(int u) 17 { 18     low[u]=pre[u]=c++; 19     sta.push(u);//!!!!!!注意 20     for(int i=0; i<g[u].size(); i++) 21     { 22         int v=g[u][i]; 23         if(!pre[v]) 24         { 25             dfs(v); 26             low[u]=min(low[u],low[v]); 27         } 28         else if(!scc_num[v]) 29             low[u]=min(low[u],pre[v]); 30     } 31     if(low[u]==pre[u]) 32     { 33         scc_count++; 34         while(1) 35         { 36             int t=sta.top(); 37             sta.pop(); 38             scc_num[t]=scc_count; 39             if(t==u) 40                 break; 41         } 42     } 43 } 44 void tranjan(int n) 45 { 46     memset(pre,0,sizeof(pre)); 47     memset(scc_num,0,sizeof(scc_num)); 48     memset(scc_value,0,sizeof(scc_value)); 49     c=1; 50     scc_count=0;  // 强连通个数     1-----scc_count 51     for(int i=0; i<n; i++) 52     { 53         if(pre[i]==0) 54             dfs(i); 55     } 56     for(int i=0; i<n; i++) 57         scc_value[scc_num[i]]+=value[i]; 58     ////////////////////重新构图 点为1  到 scc_count 59     for(int u=0; u<n; u++) 60         for(int i=0; i<g[u].size(); i++) 61         { 62             int v=g[u][i]; 63             if(scc_num[u]!=scc_num[v])//没在同一个连通分量里 64             { 65                 int uu,vv; 66                 uu=scc_num[u]; 67                 vv=scc_num[v]; 68                 reg[uu].push_back(vv); 69             } 70         } 71 } 72  73 int spfa(int s,int n,int w) 74 { 75     queue<int> q; 76     memset(vis,false,sizeof(vis)); 77     memset(d,0,sizeof(d)); 78     d[s]=w*(-1); 79     q.push(s); 80     vis[s]=true; 81     while(!q.empty()) 82     { 83         int u,v; 84         u=q.front(); 85         q.pop(); vis[u]=false; 86         for(int i=0; i<reg[u].size(); i++) 87         { 88             v=reg[u][i]; 89             if(d[v]>(d[u]-scc_value[v])) 90             { 91                 d[v]=d[u]-scc_value[v]; 92                 if(!vis[v]) 93                 { 94                     q.push(v); 95                     vis[v]=true; 96                 } 97             } 98         } 99     }100     int minn=d[s];101     for(int i=1; i<=n; i++)102 103         if(d[i]<minn)104             minn=d[i];105     return minn;106 }107 108 int main()109 {110     int a,b,i,j,t,temp;111     scanf("%d",&t);112     while(t--)113     {114         scanf("%d%d",&n,&m);115         memset(tong,false,sizeof(tong));116         for(i=0; i<=n*m; i++)117         {118             g[i].clear();119             reg[i].clear();120         }121         int num=0;122         for(i=0; i<n; i++)123         {124             scanf("%s",s[i]);125             for(j=0; j<m; j++)126                 if( s[i][j]==‘*‘ )127                     xing[num++]=i*m+j;128         }129         for(i=0; i<n*m; i++)130         {131             a=i/m;132             b=i%m;133             if(s[a][b]==‘#‘)134                 value[i]=-INF;135             else if(s[a][b]==‘*‘)136                 value[i]=0;137             else138                 value[i]=s[a][b]-‘0‘;139             if(a+1<n)140             {141                 temp=(a+1)*m+b;142                 if(s[a+1][b]!=‘#‘)143                 {144                     g[i].push_back(temp);145                     tong[i][temp]=true;146                 }147             }148             if(b+1<m)149             {150                 temp=a*m+b+1;151                 if(s[a][b+1]!=‘#‘)152                 {153                     g[i].push_back(temp);154                     tong[i][temp]=true;155                 }156             }157         }158         for(i=0; i<num; i++)159         {160             scanf("%d%d",&a,&b);161             temp=a*m+b;162             if(s[a][b]!=‘#‘)163             {164                 g[xing[i]].push_back(temp);165                 tong[xing[i]][temp]=true;166             }167         }168         tranjan(m*n);// 求 强连通 再缩点169         int ans,startpoint;170         startpoint=scc_num[0];171         ans=spfa(startpoint,scc_count,scc_value[startpoint]);  // 对新图求最短路172         printf("%d\n",ans*(-1));173     }174     return 0;175 }