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

求解释,我对得莫名其妙

Posted by ACAccepted at 2018-11-24 09:58:10 on Problem 2312 and last updated at 2018-11-24 09:58:27
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int m,n;
int a[305][305];
bool vis[305][305];

struct Cxy
{
	int x,y;
	bool operator==(struct Cxy tmp)
	{
		if(tmp.x==x && tmp.y==y)return true;
		return false;
	}
}My_loca,trea_loca;

struct BFS
{
	struct Cxy loca;
	int step;
}tmp,top;
priority_queue<BFS> Q;
int tex[4]={1,0,-1,0};
int tey[4]={0,1,0,-1};

bool operator<(const BFS &a,const BFS &b)
{
	return a.step>b.step;//为甚麽是这样?
}

void init()
{
	memset(vis,1,sizeof(vis));
	char c;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			vis[j][i]=0;
			cin>>c;
			a[j][i]=1;
			if(c=='Y'){My_loca.x=j;My_loca.y=i;}
			else if(c=='T'){trea_loca.x=j;trea_loca.y=i;}
			else if(c=='B')a[j][i]++;
			else if(c=='S' || c=='R')a[j][i]=999999999;
		}
	}
}

bool ok(struct BFS tmp)
{
	if(tmp.step>n*m*5)return false;
	if(tmp.loca.x<1 || tmp.loca.x>m)return false;
	if(tmp.loca.y<1 || tmp.loca.y>n)return false;
	if(vis[tmp.loca.x][tmp.loca.y])return false;
	return true;
}

int bfs()
{
	tmp.step=0;tmp.loca=My_loca;
	vis[My_loca.x][My_loca.y]=1;
	Q.push(tmp);
	while(!Q.empty())
	{
		top=Q.top();Q.pop();
		if(top.loca==trea_loca)return top.step;
		for(int i=0;i<4;i++)
		{
			tmp=top;
			tmp.loca.x+=tex[i];tmp.loca.y+=tey[i];
			tmp.step+=a[tmp.loca.x][tmp.loca.y];
			if(!vis[tmp.loca.x][tmp.loca.y] && tmp.step<180005)
			{
				vis[tmp.loca.x][tmp.loca.y]=1;
				Q.push(tmp);
			}
		}
	}
	return -1;
}

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0)break;
		init();
		while(!Q.empty())Q.pop();
		printf("%d\n",bfs());
	}
	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