现在的位置: 首页 > 综合 > 正文

hdu 4531 吉哥系列故事——乾坤大挪移

2018年11月09日 ⁄ 综合 ⁄ 共 2893字 ⁄ 字号 评论关闭

解题报告人:SpringWater(GHQ)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4531

记忆化广搜 + 状态压缩:

之前超内存,后来将string字符串改为int型状态,就不超了,但是悲剧的接着超时间。

之前老是超时,后来才发现,是我检查是否合格,我用的矩阵36 * 36广搜的超时,当改为加边法来有选择的广搜之后就AC了

#include <stdio.h>  
#include <string.h>  
#include <iostream>
#include <queue>
#include <string>
#include <map>
using namespace std;

queue<int> que;
map<int, int> mmap;
queue<int> bque;
string s[3][3];
char color[36];
int Map[36][36];
int vis[36];
int two[150];
struct Edge{
	int node, next;
}edge[36 * 36];
int head[36], len;


void add_edge(int a, int b)
{
	edge[len].node = b, edge[len].next = head[a]; head[a] = len++;
	edge[len].node = a, edge[len].next = head[b]; head[b] = len++;
}
int bfs()
{
	memset(vis, 0, sizeof(vis));
	memset(two, 0, sizeof(two));
	for(int i = 0; i < 36; ++i)
	{
		if(!vis[i])
		{
			if(two[color[i]]) return 0;
			two[color[i]] = 1;
			vis[i] = 1;
			bque.push(i);
			while(!bque.empty())
			{
				int now = bque.front();
				bque.pop();
				for(int  j= head[now]; ~j; j = edge[j].next)
				{
					if((color[i] == color[edge[j].node]) && !vis[edge[j].node])
						vis[edge[j].node] = 1, bque.push(edge[j].node);	
				}
			}
		}
	}
	return 1;
}
int ok(int tt)
{
	int cnt = 0;
	len = 0;
	char temp[10];
	sprintf(temp, "%09d", tt);
	memset(head, -1, sizeof(head));
	for(int i = 0; i < 3; ++i)
	{
		for(int j = 0; j < 3; ++j)
		{
			int num = temp[i * 3 + j] - '0';
			int n = num / 3, m = num % 3;
			for(int k = 0; k < 4; ++k)
				color[cnt + k] = s[n][m][k];

			add_edge(cnt, cnt + 2);
			add_edge(cnt, cnt + 3);
			add_edge(cnt + 1, cnt + 2);
			add_edge(cnt + 1, cnt + 3);
			
			if(cnt / 4 % 3 != 2)
				add_edge(cnt + 3, cnt + 6);
			if(cnt < 24)
				add_edge(cnt + 1, cnt + 12);
			cnt += 4;
		}
	}
	return bfs();
}
void add(int tt, int now)
{
	int m[3][3], j;
	char temp[10];
	char t[10];
	sprintf(temp, "%09d", tt);
	for(int i = 0; i < 3; ++i)
	{
		for(j = 0; j < 3; ++j)
			m[i][j] = temp[i * 3 + j] - '0';
	}
	for(int i = 0; i < 3; ++i)
	{
		for( j = 0; j < 3; ++j)
		{
			if(s[m[i][j]/3][m[i][j]%3][4] == '1')
				break;
		}
		if(j < 3) continue;
		memcpy(t, temp, 10);
		char ch;
		ch = t[i * 3], t[i * 3] = t[i * 3 + 1], t[i * 3 + 1] = t[i * 3 + 2], t[i * 3 + 2] = ch;
		sscanf(t, "%d", &tt);
		if(mmap.find(tt) == mmap.end())
		{
			mmap[tt] = now;
			que.push(tt);
		}
		memcpy(t, temp, 10);
		//if(t== "180342675")
		//	cout << "ans:" << check <<"t:" << t << endl;
		ch = t[i * 3 + 2], t[i * 3 + 2] = t[i * 3 + 1],t[i * 3 + 1] = t[i * 3], t[i * 3] = ch;
		sscanf(t, "%d", &tt);
		if(mmap.find(tt) == mmap.end())
		{
			mmap[tt] = now;
			que.push(tt);
		}
		//if(t == "380264175")
		//		cout << "ans:" << check <<"t:" << t << endl;

	}

	for(int i = 0; i < 3; ++i)
	{
		for(j = 0; j < 3; ++j)
		{
			if(s[m[j][i]/3][m[j][i]%3][4] == '1')
				break;
		}
		if(j < 3) continue;
		memcpy(t, temp, 10);
		char ch;
		ch = t[i], t[i] = t[i + 3], t[i + 3] = t[i  + 6], t[i + 6] =ch;
		sscanf(t, "%d", &tt);
		if(mmap.find(tt) == mmap.end())
		{
			mmap[tt] = now;
			que.push(tt);
		}
		memcpy(t, temp, 10);
		//if(t == "380642175")
		//		cout << "ans:" << check <<"t:" <<  t << endl;

		ch = t[i + 6], t[i + 6] = t[i + 3], t[i + 3] =t[i], t[i] = ch;
		sscanf(t, "%d", &tt);
		if(mmap.find(tt) == mmap.end())
		{
			mmap[tt] = now;
			que.push(tt);
		}
	//	if(t == "018342675")
	//		cout << "ans:" << check <<"t:" << t << endl;
	//	if(t == "385260124")
	//		cout << "ans:" << check <<"t:" << t << endl;
	}
}
int main()
{
	int T;
	int cas = 0;
	for(cin >> T; T--;)
	{
		for(int i = 0; i < 3; ++i)
		{
			for(int j = 0; j < 3; ++j)
			{
				cin >> s[i][j];
			}
		}
		int ans = 0;
		while(!que.empty())que.pop();
		mmap.clear();
		que.push(12345678);
		mmap[12345678] = 0;
		while(1)
		{
			int temp = que.front();
			if(ok(temp))
			{
				ans = mmap[temp];
				break;
			}
			else
				add(temp, mmap[temp] + 1);
			que.pop();
		}
		cout <<"Case #" << ++cas << ": " << ans << endl;
	}
	return 0;
}

抱歉!评论已关闭.