/ Randle /

记录详情

Memory Exceeded

/in/foo.cc: In function 'const int get_cha(int&)':
/in/foo.cc:12:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
# 状态 耗时 内存占用
#1 Memory Exceeded ≥107ms ≥256.0 MiB
#2 Memory Exceeded ≥90ms ≥256.0 MiB
#3 Memory Exceeded ≥84ms ≥256.0 MiB
#4 Memory Exceeded ≥107ms ≥256.0 MiB
#5 Memory Exceeded ≥82ms ≥256.0 MiB
#6 Memory Exceeded ≥97ms ≥256.0 MiB
#7 Memory Exceeded ≥78ms ≥256.0 MiB
#8 Memory Exceeded ≥100ms ≥256.0 MiB
#9 Memory Exceeded ≥79ms ≥256.0 MiB
#10 Memory Exceeded ≥99ms ≥256.0 MiB

代码

#include<bits/stdc++.h>
const int maxn=4e8;
int color[5],step[maxn],col_loc[5];
inline const int get_cha(int &a)
{
	char c=getchar();
	while(c<'a'||c>'z')c=getchar();
	if(c=='R'){a=1;color[1]++;}
	if(c=='G'){a=2;color[2]++;}
	if(c=='B'){a=3;color[3]++;}
	if(c=='O'){a=4;color[4]++;}
}
int s[10];
inline const int cantor()
{
	int a=0;
	for(int i=1;i<=9;i++)a=(a<<1)+(a<<3)+s[i];
	return a;
}
inline const void ex_cantor(int a)
{
	for(int i=9;i>=1;i--){s[i]=a%10;a/=10;}
}
std::set<int> been;
std::queue<int> que;
class condition
{
	public:
		int a[5],move;
}f[10];
inline const int location(int num,int loc)
{
	return (num<<1)+(num<<3)+loc;
}
inline const void get_start(int num,int loc)
{
	col_loc[f[num].a[loc]]=location(num,loc);
}
bool col_been[100];
inline const int dfs(int loc)
{
	int sum=1;
	col_been[loc]=true;
	int num=loc/10,to=loc%10;
	if(to==1)
	{
		if(num/3&&f[num-3].a[2]==f[num].a[1]&&!col_been[location(num-3,2)])sum+=dfs(location(num-3,2));
		if(f[num].a[2]==f[num].a[1]&&!col_been[location(num,2)])sum+=dfs(location(num,2));
		if(f[num].a[3]==f[num].a[1]&&!col_been[location(num,3)])sum+=dfs(location(num,3));
		if(f[num].a[4]==f[num].a[1]&&!col_been[location(num,4)])sum+=dfs(location(num,4));
	}
	if(to==2)
	{
		if(num<7&&f[num+3].a[1]==f[num].a[2]&&!col_been[location(num+3,1)])sum+=dfs(location(num+3,1));
		if(f[num].a[1]==f[num].a[2]&&!col_been[location(num,1)])sum+=dfs(location(num,1));
		if(f[num].a[3]==f[num].a[2]&&!col_been[location(num,3)])sum+=dfs(location(num,3));
		if(f[num].a[4]==f[num].a[2]&&!col_been[location(num,4)])sum+=dfs(location(num,4));
	}
	if(to==3)
	{
		if(num%3!=1&&f[num-1].a[4]==f[num].a[3]&&!col_been[location(num-1,4)])sum+=dfs(location(num-1,4));
		if(f[num].a[2]==f[num].a[3]&&!col_been[location(num,2)])sum+=dfs(location(num,2));
		if(f[num].a[1]==f[num].a[3]&&!col_been[location(num,1)])sum+=dfs(location(num,1));
		if(f[num].a[4]==f[num].a[3]&&!col_been[location(num,4)])sum+=dfs(location(num,4));
	}
	if(to==4)
	{
		if(num%3&&f[num+1].a[3]==f[num].a[4]&&!col_been[location(num+1,3)])sum+=dfs(location(num+1,3));
		if(f[num].a[2]==f[num].a[4]&&!col_been[location(num,2)])sum+=dfs(location(num,2));
		if(f[num].a[3]==f[num].a[4]&&!col_been[location(num,3)])sum+=dfs(location(num,3));
		if(f[num].a[1]==f[num].a[4]&&!col_been[location(num,1)])sum+=dfs(location(num,1));
	}
	return sum;
}
inline const bool succeed()
{
	for(int i=1;i<=4;i++)
	{
		if(!color[i])continue;
		memset(col_been,false,sizeof(col_been));
		if(dfs(col_loc[i])<color[i])return false;
	}
	return true;
}
inline const bool left(int line)
{
	for(int i=1;i<=3;i++)if(f[(line-1)*3+i].move==-1)return false;
	std::swap(s[(line-1)*3+1],s[(line-1)*3+3]);
	std::swap(s[(line-1)*3+1],s[(line-1)*3+2]);
	return true;
}
inline const bool up(int row)
{
	for(int i=1;i<=3;i++)if(f[(i-1)*3+row].move==-1)return false;
	std::swap(s[row],s[6+row]);
	std::swap(s[3+row],s[row]);
	return true;
}
void bfs()
{
	while(!que.empty())
	{
		int k=que.front();
		if(succeed()){std::cout<<step[k];exit(0);}
		ex_cantor(k);
		for(int i=1;i<=3;i++)
		{
			if(left(i))
			{
				int to=cantor();
				if(!been.count(to)){step[to]=step[k]+1;been.insert(to);que.push(to);}
			}
			if(up(i))
			{
				int to=cantor();
				if(!been.count(to)){step[to]=step[k]+1;been.insert(to);que.push(to);}
			}
		}
		que.pop();
	}
}
int main()
{
	memset(step,0x7f,sizeof(step));
	memset(color,0,sizeof(color));
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
		{
			s[(i-1)*3+j]=(i-1)*3+j;
			for(int k=1;k<=4;k++){get_cha(f[(i-1)*3+j].a[k]);get_start((i-1)*3+j,k);}
			std::cin>>f[(i-1)*3+j].move;
		}
	int k=cantor();
	step[k]=0;que.push(k);been.insert(k);
	bfs();
	return 0;
}

信息

递交者
类型
递交
题目
乾坤 T3
题目数据
下载
语言
C++
递交时间
2017-10-01 20:19:05
评测时间
2017-10-01 20:19:05
评测机
分数
0
总耗时
≥928ms
峰值内存
≥256.0 MiB