Submission #3773988

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int dp(int x,int y,int cnt);
#define INF 1000000000
int dx[]={0,1,1,1,0,-1};
int dy[]={-1,-1,0,1,1,0};
int h,w,sx,sy;
char mp[109][109];
int memo[109][109][10009];

int main(){
  memset(memo,-1,sizeof(memo));
  cin>>h>>w;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>mp[i][j];
      if(mp[i][j]=='s'){
	sx=j;
	sy=i;
	mp[i][j]='0';
      }
    }
  } 
  cout<<dp(0,0,0)<<endl;
  return(0);
}

int dp(int x,int y,int cnt){
  int rec=INF;
  if(memo[x][y][cnt]!=-1)return memo[x][y][cnt];
  if(mp[y][x]=='t')return 0;
  if(cnt>h*w)return INF;
  for(int i=0;i<6;i++){
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(0<=nx&&nx<w&&0<=ny&&ny<h){
      rec=min(rec,dp(nx,ny,cnt+1)+mp[y][x]-'0');
    }
  }
  return memo[x][y][cnt]=rec;
}

Submission Info

Judge Result