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

终于AC了 47ms

Posted by 15211160230 at 2016-09-08 11:16:24 on Problem 2312
贡献了三个WA,原来是边界的判断写错了一个数字
#include <stdio.h>
#include <memory.h>
#include <queue>
#define MAXN 301
#define INF 0x3f3f3f3f
using namespace std;
typedef struct
{	int x;
	int y;
}Point;
Point de[MAXN][MAXN],you;
int dis[MAXN][MAXN],visited[MAXN][MAXN];
int N,M;
char G[MAXN][MAXN];
int Distance(int i,int j)
{	if(G[i][j]=='B')	return 2;
	return 1;
}
bool Judge(int x,int y)
{	if(G[x][y]=='S'||G[x][y]=='R')
		return false;
	if(x<1||x>N||y<1||y>M)
		return false;
	return true;
}
void spfa()
{	queue<Point>q;
	Point temp,semp;
	int i,j,x,y,t;
	memset(visited,0,sizeof(visited));
	memset(dis,0x3f,sizeof(dis));
	q.push(you),visited[you.x][you.y]=1,dis[you.x][you.y]=0;
	while(!q.empty())
	{	temp=q.front();
		q.pop();
		visited[temp.x][temp.y]=0;
		for(i=1;i<=4;++i)
		{	if(i==1&&Judge(temp.x-1,temp.y))
			{	if(dis[temp.x-1][temp.y]>(t=dis[temp.x][temp.y]+
					Distance(temp.x-1,temp.y)))
				{	dis[temp.x-1][temp.y]=t;
					if(!visited[temp.x-1][temp.y])
					{	visited[temp.x-1][temp.y]=1;
						semp=temp;
						semp.x--;
						q.push(semp);
					}
				}	
			}
			else if(i==2&&Judge(temp.x,temp.y-1))
			{	if(dis[temp.x][temp.y-1]>(t=dis[temp.x][temp.y]+
					Distance(temp.x,temp.y-1)))
				{	dis[temp.x][temp.y-1]=t;
					if(!visited[temp.x][temp.y-1])
					{	visited[temp.x][temp.y-1]=1;
						semp=temp;
						semp.y--;
						q.push(semp);
					}
				}	
			}
			else if(i==3&&Judge(temp.x+1,temp.y))
			{	if(dis[temp.x+1][temp.y]>(t=dis[temp.x][temp.y]+
					Distance(temp.x+1,temp.y)))
				{	dis[temp.x+1][temp.y]=t;
					if(!visited[temp.x+1][temp.y])
					{	visited[temp.x+1][temp.y]=1;
						semp=temp;
						semp.x++;
						q.push(semp);
					}
				}
			}
			else if(i==4&&Judge(temp.x,temp.y+1))
			{	if(dis[temp.x][temp.y+1]>(t=dis[temp.x][temp.y]+
					Distance(temp.x,temp.y+1)))
				{	dis[temp.x][temp.y+1]=t;
					if(!visited[temp.x][temp.y+1])
					{	visited[temp.x][temp.y+1]=1;
						semp=temp;
						semp.y++;
						q.push(semp);
					}
				}
			}
		}
	}	
}
int main()
{	int i,j;
	Point target;
	while(scanf("%d %d",&N,&M)!=EOF)
	{	if(N==0&&M==0)	break;
		getchar();
		for(i=1;i<=N;++i)
		{	for(j=1;j<=M;++j)
			{	scanf("%c",&G[i][j]);
				if(G[i][j]=='Y')		you.x=i,you.y=j;
				else if(G[i][j]=='T')	target.x=i,target.y=j;
			}				
			getchar();
		}
		spfa();
		if(dis[target.x][target.y]!=INF)
				printf("%d\n",dis[target.x][target.y]);
		else	puts("-1");
	}
	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