首页 > ACM题库 > HDU-杭电 > HDU 4636-Painting the Football[解题报告]HOJ
2015
09-17

HDU 4636-Painting the Football[解题报告]HOJ

Painting the Football

问题描述 :

The football, well known as a worldwide popular sport, is made of 12 regular pentagons and 20 regular hexagons.
Strongly connected

In this problem, L has to color a new football. The football is totally white in the beginning and L has to color some of its faces into black (maybe zero). Look at the picture below, the 32 faces of a football are numbered from 1 to 32. Two faces are considered connected if and only if they share a same side such like 12 and 13 as well as 29 and 30. Each step L can choose some connected faces of the football and color all these faces into black or white no matter what color it used to be. For example, L can color the faces 2, 3, 4 and 5 at the same time, but he can’t color the faces 26 and 29 at the same time.
Strongly connected

Now give the target state of the football, your task is calculating the minimum steps that L needs to do.

输入:

The first line of the date is an integer T, which is the number of the text cases.
Then T cases follow describe a target state. Each case contains 32 integers in a line. If the ith number in this line is 1, it means that the face with index i need to color to black, otherwise it need to color to white.

输出:

The first line of the date is an integer T, which is the number of the text cases.
Then T cases follow describe a target state. Each case contains 32 integers in a line. If the ith number in this line is 1, it means that the face with index i need to color to black, otherwise it need to color to white.

样例输入:

2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1

样例输出:

Case 1: 1
Case 2: 2
Hint
Some useful information: In the original football, the face 1 and face 13 is connected, the face 13 and face 17 are connected, the face 17 and face 32 are connected, the face 15 and face 32 are connected and the face 19 and face 32 are connected. If you are still lack of imagination, maybe the follow links may help you: http://www1.esgweb.net/Article/UploadFiles09/200810/2008101900394743.gif http://www1.esgweb.net/Article/UploadFiles09/200810/2008101900394998.gif http://www.3dcadbrowser.com/download.aspx?3dmodel=21288

/* 鍏堟妸鐩搁偦鐨勪笢涓滃叏閮ㄦ悶鍑烘潵锛岀劧鍚庢悳绱㈢櫧鑹叉湁澶氬皯鍧楋紙涓嶇畻涓�涓殑锛夛紝榛戣壊鏈夊灏戝潡
 * 鐒跺悗姣旇緝濡傛灉榛戣壊鐨勪袱鍧椾互鍐呯洿鎺ュ啓鍑虹瓟妗堬紝鍚﹀垯濡傛灉鐧借壊杩炲湪涓�璧峰垯鍙涓ゆ
 * 鍚﹀垯闇�瑕�3娆�
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))

using namespace std;
vector <int>v[40];
inline void v_pb(int a,int b){
	v[a].push_back(b);
}
int num[40];
queue<int>q;
bool vis[40];
bool bfs(int s,int flag){
	while(!q.empty()) q.pop();
	q.push(s);
	int cnt = -1;
	while(!q.empty()){
		int k = q.front(); q.pop();
		cnt++;
		for (int i = 0; i < v[k].size(); i++){
			int d = v[k][i];
			if (!vis[d] && num[d] == flag){
				vis[d] = 1;
				q.push(d);
			}
		}
	}
	if(flag == 0 && cnt == 0)return 1;
	return 0;
}

int main(){
	v_pb(1,2);v_pb(1,3);v_pb(1,17);v_pb(1,18);v_pb(1,20);v_pb(1,13);
    v_pb(2,1);v_pb(2,3);v_pb(2,4);v_pb(2,7);v_pb(2,12);v_pb(2,13);
    v_pb(3,1);v_pb(3,2);v_pb(3,4);v_pb(3,5);v_pb(3,20);
	v_pb(4,2);v_pb(4,3);v_pb(4,5);v_pb(4,6);v_pb(4,7);v_pb(4,8);
    v_pb(5,3);v_pb(5,4);v_pb(5,6);v_pb(5,20);v_pb(5,21);v_pb(5,24);
    v_pb(6,4);v_pb(6,5);v_pb(6,8);v_pb(6,9);v_pb(6,24);
    v_pb(7,2);v_pb(7,4);v_pb(7,8);v_pb(7,10);v_pb(7,12);
    v_pb(8,4);v_pb(8,6);v_pb(8,7);v_pb(8,9);v_pb(8,10);v_pb(8,11);
    v_pb(9,6);v_pb(9,8);v_pb(9,11);v_pb(9,24);v_pb(9,26);v_pb(9,27);
    v_pb(10,7);v_pb(10,8);v_pb(10,11);v_pb(10,12);v_pb(10,14);v_pb(10,16);
    v_pb(11,8);v_pb(11,9);v_pb(11,10);v_pb(11,16);v_pb(11,27);
    v_pb(12,2);v_pb(12,7);v_pb(12,10);v_pb(12,13);v_pb(12,14);v_pb(12,15);
	v_pb(13,12);v_pb(13,15);v_pb(13,2);v_pb(13,1);v_pb(13,17);
    v_pb(14,10);v_pb(14,12);v_pb(14,15);v_pb(14,16);v_pb(14,30);
    v_pb(15,12);v_pb(15,13);v_pb(15,14);v_pb(15,30);v_pb(15,32);v_pb(15,17);
    v_pb(16,10);v_pb(16,11);v_pb(16,14);v_pb(16,27);v_pb(16,29);v_pb(16,30);
    v_pb(17,1);v_pb(17,18);v_pb(17,19);v_pb(17,13);v_pb(17,15);v_pb(17,32);
    v_pb(18,1);v_pb(18,17);v_pb(18,19);v_pb(18,20);v_pb(18,22);
    v_pb(19,17);v_pb(19,18);v_pb(19,31);v_pb(19,22);v_pb(19,23);v_pb(19,32);
    v_pb(20,1);v_pb(20,3);v_pb(20,5);v_pb(20,18);v_pb(20,21);v_pb(20,22);
	v_pb(21,5);v_pb(21,20);v_pb(21,22);v_pb(21,24);v_pb(21,25);
    v_pb(22,19);v_pb(22,18);v_pb(22,20);v_pb(22,21);v_pb(22,23);v_pb(22,25);
    v_pb(23,19);v_pb(23,22);v_pb(23,25);v_pb(23,28);v_pb(23,31);
    v_pb(24,5);v_pb(24,6);v_pb(24,9);v_pb(24,21);v_pb(24,25);v_pb(24,26);
    v_pb(25,21);v_pb(25,22);v_pb(25,23);v_pb(25,24);v_pb(25,26);v_pb(25,28);
    v_pb(26,9);v_pb(26,24);v_pb(26,25);v_pb(26,27);v_pb(26,28);
    v_pb(27,9);v_pb(27,11);v_pb(27,16);v_pb(27,26);v_pb(27,28);v_pb(27,29);
    v_pb(28,25);v_pb(28,26);v_pb(28,27);v_pb(28,29);v_pb(28,31);v_pb(28,23);
    v_pb(29,16);v_pb(29,27);v_pb(29,28);v_pb(29,30);v_pb(29,31);
    v_pb(30,14);v_pb(30,15);v_pb(30,16);v_pb(30,29);v_pb(30,31);v_pb(30,32);
    v_pb(31,28);v_pb(31,29);v_pb(31,30);v_pb(31,32);v_pb(31,23);v_pb(31,19);
	v_pb(32,30);v_pb(32,31);v_pb(32,15);v_pb(32,19);v_pb(32,17);
	int t;
	scanf("%d", &t);
	for (int cas = 1; cas <= t; cas++){
		printf("Case %d: ", cas);
		int black = 0,white = 0;
		for (int i = 1; i <= 32; ++i){
			scanf("%d", &num[i]);
			if(num[i]) black ++;
		}
		if (black == 0) {puts("0");continue;}
		memset(vis,0,sizeof(vis));
		black = 0;
		for (int i = 1; i <= 32; ++i){
			if (!vis[i]){
				vis[i] = 1;
				if (num[i]){
					black ++;
					bfs(i,1);
				}else {
					white ++;
					if(bfs(i,0)) white --;
				}
			}
		}
		if(black <= 2) printf("%d\n", black);
		else if (white == 1) puts("2");
		else puts("3");
	}
	return 0;
}