bzoj3109【CQOI2013】新数独

Description

Input

Output

Sample Input

Sample Output

dfs的剪枝优化，读入有点麻烦，细心就好了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define HK_reporter main
using namespace std;
int a[10][10],fh[10][10],fl[10][10];
bool flag,vsth[10][10],vstl[10][10],vst[10][10];
inline bool judge(char ch)
{
	return ch==‘<‘||ch==‘>‘||ch==‘v‘||ch==‘^‘;
}
inline void readh(int x)
{
	char ch;
	F(i,1,6)
	{
		ch=getchar();
		while (!judge(ch)) ch=getchar();
		fh[x][(i-1)/2+i]=(ch==‘>‘)?1:0;
	}
}
inline void readl(int x)
{
	char ch;
	F(i,1,9)
	{
		ch=getchar();
		while (!judge(ch)) ch=getchar();
		fl[x][i]=(ch==‘v‘)?1:0;
	}
}
inline void pre()
{
	memset(fh,-1,sizeof(fh));
	memset(fl,-1,sizeof(fl));
	F(i,1,3)
	{
		readh((i-1)*3+1);
		readl((i-1)*3+1);
		readh((i-1)*3+2);
		readl((i-1)*3+2);
		readh((i-1)*3+3);
	}
}
inline int num(int x,int y)
{
	return (x-1)/3*3+(y-1)/3+1;
}
inline void dfs(int x,int y)
{
	if (y>9) x++,y=1;
	if (x>9)
	{
		F(i,1,9)
		{
			F(j,1,8) printf("%d ",a[i][j]);
			printf("%d\n",a[i][9]);
		}
		flag=true;
		return;
	}
	F(i,1,9) if (!vsth[x][i]&&!vstl[y][i]&&!vst[num(x,y)][i])
	{
		if (fl[x-1][y]==0&&a[x-1][y]>=i) continue;
		if (fl[x-1][y]==1&&a[x-1][y]<=i) continue;
		if (fh[x][y-1]==0&&a[x][y-1]>=i) continue;
		if (fh[x][y-1]==1&&a[x][y-1]<=i) continue;
		vsth[x][i]=vstl[y][i]=vst[num(x,y)][i]=true;
		a[x][y]=i;
		dfs(x,y+1);
		if (flag) return;
		vsth[x][i]=vstl[y][i]=vst[num(x,y)][i]=false;
	}
}
int HK_reporter()
{
	pre();
	dfs(1,1);
	return 0;
}