當前位置:首頁 > 資訊 > info6 > 正文

zoj 1788 Quad Trees

發表于: 2014-05-10   作者:chen_xinjia   來源:轉載   瀏覽:
ZOJ
摘要: zoj1788先輸入初始化MAP,然后要根據MAP建立一個四分樹,自下而上建立,先建立完整的一棵樹,然后根據四個相鄰的格值相同則進行合并,(這又是遞歸的偉大),逐次向上遞歸四分樹建立完后,再進行一深度優先遍歷,生成二進制字符串,再轉化為16進制輸出//#include"stdafx.h" #include #include #include #include #include"stdio.h" u

zoj 1788

先輸入初始化MAP ,然后要根據MAP 建立一個四分樹,自下而上建立,先建立完整的一棵樹,然后根據四個相鄰的格 值相同則進行合并,(這又是遞歸的偉大),逐次向上遞歸

四分樹建立完后,再進行一深度優先遍歷,生成二進制字符串,再轉化為16進制輸出


//#include "stdafx.h"
#include <string.h>
#include <string>
#include <queue>
#include <iostream>
#include "stdio.h"
using namespace std;
char MAP[512][512];
class quadtree//結點
{
public:
	char value[3];// "00"->all 0 ,"01"->all 1,"1"->mixed
	quadtree*q[4];//four children
	quadtree()
	{
		q[0] = q[1] = q[2] = q[3] = 0;//initialize four children 
	}
	bool operator == (const quadtree &p)const//運算符重載,
	{
		if (strcmp(value, "1") == 0 || strcmp(value, p.value) != 0)
			return 0;
		else
			return 1;
	}

};
quadtree * DFS(int r, int c, int s)//r ,c 坐標,s長度
{
	int i; bool f = 1;
	quadtree*temp = new quadtree;
	if (s==1)//最小長度,每一個格
	{
		temp->value[0] = '0';
		temp->value[1] =  MAP[r][c];
		temp->value[2] = 0;//串結束符號?
		return temp;

	}
	s /= 2;//四分
	temp->q[0] = DFS(r, c, s);
	temp->q[1] = DFS(r, c + s, s);
	temp->q[2] = DFS(r + s, c, s);
	temp->q[3] = DFS(r + s, c + s, s);
	for (i = 1; i < 4;i++)
	{
		if(!(*temp->q[0] == *temp->q[i]))//some of four children are different ,can not be merged
		{
			f = 0;
			break;
		}
	}
	if (f)//all children are same,merge
	{
		strcpy(temp->value, temp->q[0]->value);
		for (i = 0; i < 4; i++)
			{
			delete temp->q[i]; temp->q[i] = 0;//delete all children 
			}
	}
	else// don't merge
	{
		strcpy(temp->value, "1");
	}
	return temp;
}
string BFS(quadtree*root)//廣度遍歷,生成二進制字符串
{
	string s = "";
	quadtree *cur = root;
	queue <quadtree*> que;
	que.push(root);
	while (!que.empty())
	{
		cur = que.front();
		que.pop();
		s += cur->value;
		for (int i = 0; i < 4; i++)
		{
			if (cur->q[i]->value != NULL)//有子才放進去!!!!!!!
			que.push(cur->q[i]);
		}
	}
	return s;
}
//////////////////////////////////////////////
//轉化為16進制。。別人家的代碼
char tohex(const string& str)
{
	int ret = 0;

	for (int i = 0; i < 4; i++) 
	{
		ret <<= 1;//左移 實現16進制的轉化
		if (str[i] == '1')
			++ret;
	}

	return (ret < 10) ? '0' + ret : 'A' + ret - 10;
}
string ToHex(const string& str)
{
	string tmp = str;
	string ret = "";

	while (tmp.length() % 4 != 0)
		tmp = "0" + tmp;
	for (size_t i = 0; i < tmp.length(); i += 4)
		ret += tohex(tmp.substr(i, 4));//substr 截取指定字符串,i為起始位置,4表示長度

	return ret;
}
////這部分是別人家的 = =
///////////////////////////////////////////////////
int  main()
{
	string al;
	int k, N;
	scanf("%d", &k);//輸入test 次數
	while (k--)
	{
		scanf("%d", &N);
		for (int i = 0; i < N; i++)//輸入矩陣大小
		{
			for (int  j = 0; j < N; j++)
			{
				cin >> MAP[i][j];// scanf("%c", &MAP[i][j]);//initialize the array
				
			}
	
		}
		quadtree *root;
		root =DFS(0, 0, N);//build a quardtree;
		al = BFS(root);
		//cout << al << endl;
		cout << ToHex(al) << endl;
	}
	return 0;
}




zoj 1788 Quad Trees

版權所有 IT知識庫 CopyRight ? 2009-2015 IT知識庫 IT610.com , All Rights Reserved. 京ICP備09083238號
广东25选5开奖结果