| ||||||||||
| 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