方法一:dp(卡memset)
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[505],w[505],dp[505][505];
char mp[505][505];
int32_t main(){
freopen("balls.in","r",stdin);
int T;
cin>>T;
while(T--){
int n,m;
cin>>n>>m;
for(int i=1;i<=500;i++){
for(int j=1;j<=500;j++){
dp[i][j]=0;
}
}
for(int i=1;i<=m;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
for(int i=1;i<=m;i++){
cin>>w[i];
dp[n+1][i]=w[i];
}
int ans=0;
for(int i=n;i>=1;i--){
for(int j=1;j<=m;j++){
if(mp[i][j]=='.'){
dp[i][j]=dp[i+1][j];
}
else{
dp[i][j]=max(dp[i+1][j],max(dp[i+1][j-1],dp[i+1][j+1]));
}
}
}
for(int i=1;i<=m;i++){
ans+=dp[1][i]*a[i];
}
cout<<ans<<endl;
}
return 0;
}
方法二:bfs
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int x;
int id;
}w[505];
int a[505],vis[505][505];
char mp[505][505];
bool comp(node u,node v){
return u.x>v.x;
}
struct nodee{
int x;
int y;
};
int32_t main(){
int T;
cin>>T;
while(T--){
int n,m;
cin>>n>>m;
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
for(int i=1;i<=m;i++){
cin>>w[i].x;
w[i].id=i;
}
sort(w+1,w+1+m,comp);
int ans=0;
for(int i=1;i<=m;i++){
queue<nodee> q;
q.push({n+1,w[i].id});
while(!q.empty()){
nodee now=q.front();
if(now.x==0) break;
q.pop();
if(now.y-1>0&&(mp[now.x-1][now.y-1]=='/'||mp[now.x-1][now.y-1]=='\\')&&!vis[now.x-1][now.y-1]){
q.push({now.x-1,now.y-1});
vis[now.x-1][now.y-1]=1;
}
if(now.y+1<=m&&(mp[now.x-1][now.y+1]=='/'||mp[now.x-1][now.y+1]=='\\')&&!vis[now.x-1][now.y+1]){
q.push({now.x-1,now.y+1});
vis[now.x-1][now.y+1]=1;
}
if(!vis[now.x-1][now.y]){
q.push({now.x-1,now.y});
vis[now.x-1][now.y]=1;
}
}
while(!q.empty()){
nodee tem=q.front();
q.pop();
ans+=w[i].x*a[tem.y];
}
}
cout<<ans<<endl;
}
return 0;
}