Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
1691广度优先搜索,自己能想出来的测试数据都能过,但还是WA~~~~哪位牛人帮忙测试测试~~~~先谢谢了~~~~ //#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator