但是一样的代码spoj用时400ms,uva用时3000ms是怎么回事，bug了吗。

题目1

题目2

输入方式的略微不同我改了。我看了很多题解的优化方式好像也没不同啊。

代码如下：

#pragma GCC optimize(2) 
#include<bits/stdc++.h>
using namespace std;
const int N=1<<16,M=18;
char s[M][M];
int num[N],cnt[N],fe[M][M];
inline void update(int x,int y,int z) 
{
	for(int i=1; i<=16; i++)
	{
		fe[x][i]&=~(1<<z);
		fe[i][y]&=~(1<<z);
	}
	int stx=(x-1)/4*4+1,sty=(y-1)/4*4+1;
	for(int i=stx; i<stx+4; i++)
	{
		for(int j=sty; j<sty+4; j++)
			fe[i][j]&=~(1<<z);
	}

}

bool dfs(int left)
{
	if(!left)
	{
		for(int i=1; i<=16; i++) printf("%s\n",s[i]+1);
		return 1;
	}

	int fe_save[M][M];
	memcpy(fe_save,fe,sizeof(fe_save));

	int mn=17,nx,ny;
	for(int i=1; i<=16; i++) 
	{
		for(int j=1; j<=16; j++)
		{
			if(s[i][j]!='-') continue;
			if(!fe[i][j]) return 0;
			if(cnt[fe[i][j]]==1)
			{
				s[i][j]=num[fe[i][j]]+'A';
				update(i,j,num[fe[i][j]]);

				if(dfs(left-1)) return 1;
				s[i][j]='-';
				memcpy(fe,fe_save,sizeof(fe_save));
				return 0;
			}
			if(cnt[fe[i][j]]<mn)
			{
				mn=cnt[fe[i][j]];
				nx=i;
				ny=j;
			}
		}
	}

	for(int i=1; i<=16; i++)   
	{
		int vis=0,now_left=0;
		for(int j=1; j<=16; j++) 
		{
			if(s[i][j]=='-') now_left++;
			else vis|=1<<(s[i][j]-'A');
		}
		if(!now_left) continue;
		for(int j=0; j<16; j++)
		{
			if(vis>>j&1) continue;
			int cntt=0,last;
			for(int k=1; k<=16; k++)
			{
				if(s[i][k]!='-') continue;
				if(!(fe[i][k]>>j&1)) continue;
				cntt++;
				last=k;
				if(cntt>=2) break;
			}
			if(!cntt) return 0;
			if(cntt==1)
			{
				s[i][last]=j+'A';
				update(i,last,j);
				if(dfs(left-1))return 1;
				s[i][last]='-';
				memcpy(fe,fe_save,sizeof(fe_save));
				return 0;
			}
		}
	}

	for(int i=1; i<=16; i++) 
	{
		int vis=0,now_left=0;
		for(int j=1; j<=16; j++)  
		{
			if(s[j][i]=='-') now_left++;
			else vis|=1<<(s[j][i]-'A');
		}
		if(!now_left) continue;
		for(int j=0; j<16; j++)
		{
			if(vis>>j&1) continue;
			int cntt=0,last;
			for(int k=1; k<=16; k++)
			{
				if(s[k][i]!='-') continue;
				if(!(fe[k][i]>>j&1)) continue;
				cntt++;
				last=k;
				if(cntt>=2) break;
			}
			if(!cntt) return 0;
			if(cntt==1)
			{
				s[last][i]=j+'A';
				update(last,i,j);
				if(dfs(left-1))return 1;
				s[last][i]='-';
				memcpy(fe,fe_save,sizeof(fe_save));
				return 0;
			}
		}
	}
	for (int x=1; x<=13; x+=4)
	{
		for (int y=1; y<=13; y+=4)
		{
			int vis=0,now_left=0;
			for (int i=x; i<x+4; i++)
			{
				for (int j=y; j<y+4; j++)
				{
					if (s[i][j]=='-') now_left++;
					else vis|=1<<(s[i][j]-'A');
				}
			}
			if (!now_left) continue; 
			for (int k=0; k<16; k++)   
			{
				if (vis>>k&1) continue;
				int cntt=0,lastx,lasty;
				for (int i=x; i<x+4; i++)
				{
					for (int j=y; j<y+4; j++)
					{
						if (s[i][j]!='-') continue;
						if (!(fe[i][j]>>k&1)) continue;
						cntt++;
						lastx=i;
						lasty=j;
					}
				}
				if (!cntt) return 0;
				if (cntt==1)
				{
					s[lastx][lasty]=k+'A';
					update(lastx,lasty,k);
					if (dfs(left-1)) return 1;
					s[lastx][lasty]='-';
					memcpy(fe,fe_save,sizeof(fe_save));
					return 0;
				}
			}
		}
	}
	for (int i=fe[nx][ny]; i; i-=i&-i) 
	{
		int z=num[i&-i];
		s[nx][ny]=z+'A';
		update(nx,ny,z);
		if (dfs(left-1)) return 1;
		s[nx][ny]='-';
		memcpy(fe,fe_save,sizeof(fe));
	}
	return 0;
}

int T=0;
int main()
{
	for(int i=0;i<16;i++) num[1<<i]=i;
	for(int i=0;i<N;i++)
	{
		for(int j=i; j; j-=j&-j)
			cnt[i]++;
	}
	while(scanf("%s",s[1]+1))
	{
		if(T) puts("");
		T=1;
		
		for(int i=2;i<=16;i++)
			scanf("%s",s[i]+1);
		for(int i=1; i<=16; i++)
		{
			for(int j=1; j<=16; j++)
				fe[i][j]=N-1;
		}
		int left=0;
		for(int i=1;i<=16; i++)
		{
			for(int j=1;j<=16;j++)
			{
				if(s[i][j]=='-') left++;
				else update(i,j,s[i][j]-'A');
			}
		}
		dfs(left);
	}
}