提出 #1625320

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define int long long
#define N 55
using namespace std;
const int INF = 1LL<<55;
int Max(int &a,int b){return a=max(a,b);}
int Min(int &a,int b){return a=min(a,b);}
int h,w;
string mp[N];
int dx[] = {0,1};
int dy[] = {1,0};

int mem1[N][N][N][N],used1[N][N][N][N];
int dfs1(int y,int x,int gy,int gx){
  int num1 = mp[y][x] - '0';  
  if(y == gy && x == gx) return num1;
  if(used1[y][x][gy][gx]++) return mem1[y][x][gy][gx];


  int res = -1;
  for(int i=0;i<2;i++){
    for(int j=0;j<2;j++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      int nnx = nx + dx[j];
      int nny = ny + dy[j];
      int num2 = mp[nny][nnx] - '0';
      char en = mp[ny][nx];
      if(nnx > gx || nny > gy)continue;
      if(en == '*')  Max(res,num1 * dfs1(nny,nnx,gy,gx));
      if(en == '+')  dfs1(nny,nnx,gy,gx);
      Min(res,INF);
    }
  }
  return mem1[y][x][gy][gx] = res;
}

int mem2[N][N][2],used2[N][N][2];
int dfs2(int y,int x,int f){
  int num1 = mp[y][x] - '0';
  if(y == h-1 && x == w-1) return f? 0:num1;
  if(used2[y][x][f]++) return mem2[y][x][f];
  
  int res = 0;
  for(int i=0;i<2;i++){
    for(int j=0;j<2;j++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      int nnx = nx + dx[j];
      int nny = ny + dy[j];
      if(nnx >= w || nny >= h || mp[ny][nx] != '+') continue;
      if(f == 0)  Max(res,num1 + dfs2(nny,nnx,0));
      else Max(res,dfs2(nny,nnx,0));
    }
  }

  if(f == 0){
    for(int ny=y;ny<h;ny++)
      for(int nx=x;nx<w;nx++){
	if((nx+ny)%2 == 1 || (nx == x && ny == y)) continue;
	dfs1(y,x,ny,nx);
	if(mem1[y][x][ny][nx]==-1)continue;
	Max(res,mem1[y][x][ny][nx] + dfs2(ny,nx,1));
      }
  }
  return mem2[y][x][f] = min(res,INF);
}

signed main (){

  cin>>h>>w;
  for(int i=0;i<h;i++) cin>>mp[i];
  
  //  for(int i=0;i<h;i++)
  //for(int j=0;j<w;j++) dfs1(0,0,i,j);

  
  int ans = max(dfs2(0,0,0),dfs2(0,0,1));
  if(ans > (int)1e15) ans = -1;
  cout<<ans<<endl;

  return 0;
}

提出情報

ジャッジ結果