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

C++ AC,G++ WA,why?

Posted by Yinthewind at 2012-04-07 17:38:20 on Problem 2056
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define MAXN 202

class point
{
	public:
		int x,y;
		point(){}
		point(int y,int x):y(y),x(x){}

};
int N,M,d[3][2]={{-1,0},{1,0},{0,1}};
int m[MAXN][MAXN],vst[MAXN][MAXN];

int bfs(int i)
{
	queue<point> q;
	point tmp(1,i);
	q.push(tmp);
	vst[1][i]=1;
	while(q.size())
	{
		point u=q.front();
		q.pop();
		for(int k=0;k<3;k++)
		{
			tmp.x=u.x+d[k][0];
			tmp.y=u.y+d[k][1];
			if(tmp.x>M or tmp.x<1) continue;
			if(tmp.y>N or tmp.y<1) continue;
			if(vst[tmp.y][tmp.x] or m[tmp.y][tmp.x]==0) continue;
			vst[tmp.y][tmp.x]=vst[u.y][u.x]+1;
			if(tmp.y==N) return vst[tmp.y][tmp.x];
			q.push(tmp);
		}
	}
}
int main()
{
	while(cin>>N>>M,N|M)
	{
		char ch;
		memset(m,0,sizeof(m));
		for(int i=N;i>=1;i--) for(int j=1;j<=M;j++)
		{
			while((ch=getchar())!='W' and ch!='S' and ch!='B');
			if(ch=='S')
			{
				m[i][j]=1;
				if((i==1 or i==N) and j<M-1) m[i][j+1]=1;
				else if(i>1 and i<N and j<M) m[i][j+1]=1;
			}
		}
		int ans=9999999;
		for(int i=1;i<=M;i++) if(m[1][i]) 
		{
			memset(vst,0,sizeof(vst));
			ans=min(bfs(i),ans);
		}
		cout<<ans<<endl;
	}
	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