| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
悲剧,dfs+记忆化,wa!求哪位路过的大牛帮忙看看#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator