Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

悲剧,dfs+记忆化,wa!求哪位路过的大牛帮忙看看

Posted by ccsu2008021220 at 2010-02-28 00:52:37 on Problem 2312
#include<stdio.h>
#include<string.h>
using namespace std;
const int Len=302;
const int inf=1<<30;
const int F[5][2]={{},{0,-1},{-1,0},{0,1},{1,0}};
#define min(a,b) (a<b?a:b)
char map[Len][Len];
int dp[Len][Len];
bool visit[Len][Len];
int m,n;
bool found;
int check(int x,int y)
{
    bool f=visit[x][y];
    if(x>=1&&x<=m&&y>=1&&y<=n&&(map[x][y]=='E'||map[x][y]=='T')&&!f) return 1;
    else if(x>=1&&x<=m&&y>=1&&y<=n&&map[x][y]=='B'&&!f) return 2;
    else return 0;
}
int dfs(int x,int y)
{
    if(dp[x][y]) return dp[x][y];
    if(map[x][y]=='T')
    {
        found=true;
        return (dp[x][y]=0);
    }
    int sum,ans=inf;
    for(int i=1;i<=4;i++)
    {
         int t=check(x+F[i][0],y+F[i][1]);
         if(t)
         {
              visit[x+F[i][0]][y+F[i][1]]=true;
              sum=t+dfs(x+F[i][0],y+F[i][1]);
              ans=min(ans,sum);
              visit[x+F[i][0]][y+F[i][1]]=false;
         }
    }
    return (dp[x][y]=ans);
}
int main()
{
    while(scanf("%d%d",&m,&n)&&(n||m))
    {
         for(int i=1;i<=m;i++)
         {
             getchar();
             for(int j=1;j<=n;j++)
                 scanf("%c",&map[i][j]);
         }
         memset(visit,0,sizeof(visit));
         memset(dp,0,sizeof(dp));
         found=false;
         int x,y;
         for(int i=1;i<=m;i++)
             for(int j=1;j<=n;j++)
                 if(map[i][j]=='Y')
                 {
                     x=i,y=j;
                     break;
                 }
         visit[x][y]=1;
         int ans=dfs(x,y);
         if(!found) printf("-1\n");
         else  printf("%d\n",ans);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator