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