http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2334
题目大意:(如题)
输入输出:(如题)
解题思路:
1.队列模拟。
2.定义结构体用于记录农民john和两头牛的信息:
 

typedef struct
{
int x;//横坐标
int y;//纵坐标
char d;//方向N,S,E,W
}pos;


3.建立两个队列qc和qf,进行模拟,满足条件的入队列
4.每次取两队首元素进行比较,如果纵坐标横坐标都相同时抓到当队列为空或者cnt>160000时说明永远无法抓到。
(状态只有(10*10*4)400种,两个人最多(400*400)160000种)
核心代码:
 

void bfs()
{
	pos tmpc,tmpf;
	while(cnt<=160000&&!qc.empty()&&!qf.empty())
	{
		tmpc=qc.front();
		qc.pop();
		tmpf=qf.front();
		qf.pop();
		if(tmpc.x==tmpf.x&&tmpc.y==tmpf.y)
			break;
		switch(tmpc.d)
		{
		case 'N':
			if(tmpc.y-1>=1&&graph[tmpc.x][tmpc.y-1]!='*')
				tmpc.y--;
			else
				tmpc.d='E';
			qc.push(tmpc);
			break;
		case 'S':
			if(tmpc.y+1<=10&&graph[tmpc.x][tmpc.y+1]!='*')
				tmpc.y++;
			else
				tmpc.d='W';
			qc.push(tmpc);
			break;
		case 'E':
			if(tmpc.x+1<=10&&graph[tmpc.x+1][tmpc.y]!='*')
				tmpc.x++;
			else
				tmpc.d='S';
			qc.push(tmpc);
			break;
		case 'W':
			if(tmpc.x-1>=1&&graph[tmpc.x-1][tmpc.y]!='*')
				tmpc.x--;
			else
				tmpc.d='N';
			qc.push(tmpc);
			break;
		default:
			break;
		}
		switch(tmpf.d)
		{
		case 'N':
			if(tmpf.y-1>=1&&graph[tmpf.x][tmpf.y-1]!='*')
				tmpf.y--;
			else
				tmpf.d='E';
			qf.push(tmpf);
			break;
		case 'S':
			if(tmpf.y+1<=10&&graph[tmpf.x][tmpf.y+1]!='*')
				tmpf.y++;
			else
				tmpf.d='W';
			qf.push(tmpf);
			break;
		case 'E':
			if(tmpf.x+1<=10&&graph[tmpf.x+1][tmpf.y]!='*')
				tmpf.x++;
			else
				tmpf.d='S';
			qf.push(tmpf);
			break;
		case 'W':
			if(tmpf.x-1>=1&&graph[tmpf.x-1][tmpf.y]!='*')
				tmpf.x--;
			else
				tmpf.d='N';
			qf.push(tmpf);
			break;
		default:
			break;
		}
		cnt++;
	}
}

发表评论

电子邮件地址不会被公开。

Post Navigation