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

1691广度优先搜索,自己能想出来的测试数据都能过,但还是WA~~~~

Posted by hohowenzi at 2007-04-05 13:33:47 on Problem 1691
哪位牛人帮忙测试测试~~~~先谢谢了~~~~

//#include<fstream>
#include<iostream>
#include<queue>
using namespace std;

/*广度优先搜索求解*/


/*存储所有矩形位置与颜色*/
struct Node{
	int y1,x1,y2,x2,color;
};
Node rectangle[15];

/*搜索队列,元素为long编码,其中0-14位表示15个矩形涂色与否,
  15-21位存储下一个待涂颜色编号,22-31位存储总上色次数    */
queue <long> codeQ;
int n;

int compare(const void *a,const void *b){
	Node *aa = (Node*)a, *bb = (Node*)b;
	return (aa->y1==bb->y1) ? (aa->x1 - bb->x1) : (aa->y1 - bb->y1);
}

/*从编码中取待涂颜色*/
int nextColor(long code){
	return (code>>15) & 31;
}

/*从编码中取总上色次数*/
int times(long code){
	return code>>22;
}

/*判断对于状态编码code,是否能在编号n的矩形上涂色*/
int isPaintable(long code,int n){
	int i;
	for(i = 0;i < n;i++){
		if(rectangle[i].y2 - rectangle[n].y1 == 0 && (rectangle[i].x1 - rectangle[n].x2)*(rectangle[i].x2 - rectangle[n].x1) < 0)
			if(((code>>i) & 1) == 0) return 0;
	}
	return 1;
}

/*对状态编码code进行一次上色,颜色为code第15-21位指定颜色
  若code至少涂上一块矩形,则返回值为1;否则返回0.
  返回时code涂色次数已加1                              */
int paint(long &code){
	int i,s = 0;
	/*对已排序矩形进行由上至下扫描,若有矩形未涂色且与待涂色
	  颜色相同,判断是否能上色,若能,则将该矩形上色*/
	for(i = 0;i < n;i++){
		if( (((code>>i)&1)==0) && rectangle[i].color==nextColor(code) && isPaintable(code,i) ){
			code += (1<<i);
			s++;
		}
	}
	if(s == 0) return 0;
	else{
		code += 1<<22;
		return 1;
	}
}	

void main(){
	//ifstream fin("in.txt");
	long code;
	int i,nCases;
	cin>>nCases;
	for(;nCases > 0;nCases--){
		//矩形数据清零
		memset(rectangle,0,sizeof(rectangle));
		//输入,排序
		cin>>n;
		for(i = 0;i < n;i++){
			cin>>rectangle[i].y1>>rectangle[i].x1;
			cin>>rectangle[i].y2>>rectangle[i].x2>>rectangle[i].color;
		}	

		/*文件输入
		fin>>n;
		for(i = 0;i < n;i++){
			fin>>rectangle[i].y1>>rectangle[i].x1;
			fin>>rectangle[i].y2>>rectangle[i].x2>>rectangle[i].color;
		}*/

		qsort(rectangle,n,sizeof(Node),compare);

		//初始化队列,将1-20号颜色标记为待涂颜色压入队列
		//涂色次数(22-31位)和矩形上色状态(0-14位)为零
		for(i = 1;i < 21;i++){
			code = i<<15;
			codeQ.push(code);
		}

		//广度优先搜索
		while(!codeQ.empty()){
			code = codeQ.front();
			codeQ.pop();
			//退出搜索条件,code第0至n-1位全为1,即所有矩形上色完毕
			if((code & (1<<15)-1) == (1<<n)-1){
				cout<<times(code)<<endl;
				break;
			}
			//若code至少涂上一块颜色,则将code的待涂颜色变为1-20号颜色,并压入队列
			if(paint(code)){
				for(i = 1;i < 21;i++){
					code &= ~(31<<15); //15-21位清零
					code += i<<15;     //更换待涂颜色
					codeQ.push(code);
				}
			}
		}
	}
}

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