本文共 2689 字，大约阅读时间需要 8 分钟。
用了两个pii代码有点长……
记忆化搜索主要还是用用dp数组去记录并更新状态
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #define cl(a,b) memset(a,b,sizeof(a)) 19 #define debug(x) cerr<<#x<<"=="<<(x)< 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 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
转载于:https://www.cnblogs.com/general10/p/6497918.html