1 #include<cstdio>  2 #include<iostream>  3 #include<algorithm>  4 #include<cmath>  5 #include<cstring>  6 #include<string>  7 #include<ctime>  8 #include<map>  9 #include<set> 10 #include<vector> 11 #include<queue> 12 #include<cstdlib> 13 #include<cassert> 14 #include<sstream> 15 #include<stack> 16 #include<list> 17 #include<bitset> 18 #define cl(a,b) memset(a,b,sizeof(a)) 19 #define debug(x) cerr<<#x<<"=="<<(x)<<endl 20 using namespace std; 21 typedef long long ll; 22 typedef long double ldb; 23 typedef pair<int,int> pii; 24  25 const int inf=0x3f3f3f3f; 26 const int maxn=12; 27 const int mod=1e7+7; 28 const double eps=1e-8; 29 const double pi=acos(-1); 30  31 int dx[8]= {-1,0,1,0,0}; 32 int dy[8]= {0,1,0,-1,0}; 33  34 int n,m,ans; 35 bool mp[maxn][maxn]; 36 int value[maxn][maxn][205]; 37 int dp[maxn][maxn][maxn][maxn][205]; 38  39 struct people 40 { 41     int time; 42     pii x,y; 43 }; 44  45 bool check(people x) 46 { 47     if(x.x.first<1||x.x.first>n) return false; 48     if(x.x.second<1||x.x.second>m) return false; 49     if(x.y.first<1||x.y.first>n) return false; 50     if(x.y.second<1||x.y.second>m) return false; 51     if(!mp[x.x.first][x.x.second]) return false; 52     if(!mp[x.y.first][x.y.second]) return false; 53     return true; 54 } 55  56 void init() 57 { 58     ans=0; 59     cl(mp,0); 60     cl(dp,-1); 61     cl(value,0); 62 } 63  64 void bfs() 65 { 66     queue<people>q; 67     while(!q.empty()) q.pop(); 68     people st; 69     st.x.first=1,st.x.second=1; 70     st.y.first=1,st.y.second=1; 71     st.time=0; 72     dp[st.x.first][st.x.second][st.y.first][st.y.second][st.time]=0; 73     q.push(st); 74     while(!q.empty()) 75     { 76         people tmp=q.front(); 77         q.pop(); 78         if(tmp.time>200) break; 79         for(int i=0;i<5;i++) 80         {//人和影子分别走 81             for(int j=0;j<5;j++) 82             { 83                 people use; 84                 use.x.first=tmp.x.first+dx[i]; 85                 use.x.second=tmp.x.second+dy[i]; 86                 use.y.first=tmp.y.first+dx[j]; 87                 use.y.second=tmp.y.second+dy[j]; 88                 use.time=tmp.time+1; 89                 if(check(use)) 90                 { 91                     int now=dp[tmp.x.first][tmp.x.second][tmp.y.first][tmp.y.second][tmp.time]; 92                     now+=value[use.x.first][use.x.second][use.time]; 93                     now+=value[use.y.first][use.y.second][use.time]; 94                     if(use.x.first==use.y.first&&use.x.second==use.y.second) 95                         now-=value[use.x.first][use.x.second][use.time]; 96                     if(now>dp[use.x.first][use.x.second][use.y.first][use.y.second][use.time]) 97                     { 98                         if(dp[use.x.first][use.x.second][use.y.first][use.y.second][use.time]==-1) 99                         {//判断是否更新过100                             q.push(use);101                         }102                         dp[use.x.first][use.x.second][use.y.first][use.y.second][use.time]=now;103                         ans=max(now,ans);104                     }105                 }106             }107         }108     }109 }110 111 int main()112 {113     int T;114     scanf("%d",&T);115     while(T--)116     {117         scanf("%d%d",&n,&m);118         init();119         char str[15];120         for(int i=1;i<=n;i++)121         {122             scanf("%s",str);123             for(int j=0;j<m;j++)124             {125                 if(str[j]==‘.‘) mp[i][j+1]=true;126             }127         }128         int num;129         scanf("%d",&num);130         for(int i=0;i<num;i++)131         {132             int t,x,y,v;133             scanf("%d%d%d%d",&t,&x,&y,&v);134             value[x][y][t]+=v; //注意要+=而不是=135         }136         bfs();137         printf("%d\n",ans);138     }139     return 0;140 }141 142 /*143 144 1145 3 3146 ...147 ..#148 ...149 3150 2 3 1 3151 2 2 2 2152 2 1 3 1153 154 */