TIOJ 1196 小豬Piggy

[動態規劃]
這次注意了一下時間 花32分鐘...應該還可以更快...

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<map.h>
#define max(a,b) (a)>(b) ? (a):(b)
bool isint(char c)
{
 return ((c<='9')&&(c>='0'));
}
int chartoint(char c)
{
 if((c=='X')||(c=='B')||(c=='A'))
  return 0;
 return c-'0';
}
void getnextline()
{
 char nl;
 nl='1';
 while(nl!='\n')
  scanf("%c",&nl);
}
int main()
{
 int n;
 while(scanf("%d",&n)==1)
 {
  char _map[n+1][n+1];
  int dp[n+1][n+1];
  bool isReach[n+1][n+1];
  memset(isReach,false,(n+1)*(n+1)*sizeof(bool));
  getnextline();
  for(int lx=1;lx<=n;lx++)
  {
   for(int ly=1;ly<=n;ly++)
    scanf("%c",&_map[lx][ly]);
   getnextline();
  }
  for(int lx=0;lx<=n;lx++){dp[lx][0]=0;dp[0][lx]=0;isReach[lx][0]=false;isReach[0][lx]=false;}
  isReach[1][1]=true;
  dp[1][1]=0;dp[n][n]=-1;
  for(int lx=1;lx<=n;lx++)
  {
   for(int ly=1;ly<=n;ly++)
   {
    if(lx+ly>2)
     isReach[lx][ly]=(isReach[lx-1][ly]||isReach[lx][ly-1]);
    if(_map[lx][ly]=='X')
    {
     dp[lx][ly]=0;
     isReach[lx][ly]=false;
    }
    else if(_map[lx][ly]=='A')
     dp[lx][ly]=0;
    else
     dp[lx][ly]=(dp[lx][ly-1]>=dp[lx-1][ly] ? dp[lx][ly-1]:dp[lx-1][ly])+chartoint(_map[lx][ly]);
    //printf("dp[%d][%d]=%d\n",lx,ly,dp[lx][ly]);
   }
  }
  dp[1][1]=0;
  /*for(int lx=1;lx<=n;lx++)
  {
   for(int ly=1;ly<=n;ly++)
    printf("%d\t",dp[lx][ly]);
   printf("\n");
  }*/
  if(isReach[n][n])
   printf("%d\n",dp[n][n]);
  else
   printf("X\n");
 }
 return 0;
}