HDU5838G.Mountain(허용+dfs+상압)

링크
nnn과 mmm의 범위는 매우 작고 상압을 고려한다
그런데 바닥이 있어서 상압이 안 돼요.
그래서 우리는 dp[i][j]dp[i][j]dp[i][j]를 작은 것부터 큰 것까지 ii 개수를 채우기 위해 밑바닥을 채운 상태는 jj라고 정의했다.
이렇게 해서 저희가 숫자 i+1 i+1 i+1을 채워야 한다면.
Ⅰ . 채워지지 않은 골짜기 I 에 채울 수 있다.채워지지 않은 골짜기 I 에 채울 수 있다.채워지지 않은 바닥을 채울 수 있어요.
Ⅱ . 채워지지 않은 골짜기 II에 채울 수 있습니다.채워지지 않은 골짜기 II에 채울 수 있습니다.채워지지 않은 비곡저에 채울 수 있어요.
하지만 꼼꼼히 생각해보면 옮기는 II의 비곡저를 충족시키려면 약간의 제한이 있지만 꼼꼼히 상상해 보세요. 옮기는 II의 비곡저를 충족시키려면 약간의 제한이 있지만 꼼꼼히 상상해 보세요. 옮기는 II의 비곡저를 충족시키려면 약간의 제한이 있습니다.
즉, 주위에 채워지지 않은 곡바닥을 함유할 수 없다. 그렇지 않으면 후속 채워진 수가 지금보다 크고 곡바닥의 요구에 부합되지 않으면 주위에 채워지지 않은 곡바닥을 함유할 수 없다. 그렇지 않으면 후속 채워진 수가 지금보다 크고 곡바닥의 요구에 부합되지 않으면 주위에 채워지지 않은 곡바닥을 함유할 수 없다. 그렇지 않으면 후속 채워진 수가 지금보다 크고 곡바닥의 요구에 부합되지 않는다.
그리고 이동하면 폭력적으로 현재 바닥의 상태를 일일이 열거하여 채우면 됩니다. 각 상태의 정보는 미리 처리할 수 있습니다.
그런데 이게 끝인가요?네이티브... 이렇게 비합법적인 상태가 들어갔어요.
예를 들어 어떤 비곡바닥은 원래 주위의 해발보다 낮을 수 없다(그렇지 않으면 곡바닥이 된다)
하지만 상소 알고리즘은 여전히 평상시대로 계산되었다!!!
자세히 생각해 보면, 만약 비곡저 주위에 곡저가 없다면, 상압 과정 중 주위의 해발보다 낮을 수 있다
예를 들어 xx위치는 곡저위치이고 yyy와zzz는 비곡저위치이다(단, 상압켄은 곡저위치로 계산될 수 있다)
그러면 x를 계산할 때 밑바닥 조합 방안이 되는 것은: x, xy, xz, xyz 그러면 x를 계산할 때, 밑바닥 조합 방안이 되는 것은: x, xy, xz, xyz 그러면 x를 계산할 때, 밑바닥 조합 방안이 되는 것은: x, xy, xz, xyz, xyz이다.
하지만 우리는 xxx만 있으면 돼, 다른 비곡바닥은 곡바닥이 될 수 없어!!!
그래서 우리는 x y xy xy를 다시 계산해서 골짜기 조합 방안이 되는 것은 f(x y): x y, x y z f(xy): xy, xyz f(xy): xy, xyz
그래서 우리는 xz xz xz를 계산하고 골짜기 조합 방안이 되는 것은 f(xz): xz, xy z f(xz): xz, xy z f(xz): xz, xy z
그래서 우리는 x yz xyz xyz를 다시 계산해서 골짜기 조합 방안이 되는 것은 f(x yz): x yz f(xyz): xyz f(xyz): xyz
그러면 x의 방안만 배척을 거치면 x=f(x)-4-f(xy)-4-f(xz)+f(xyz)면 x의 방안만 배척을 거치면 x=f(x)-f(xy)-f(xz)+f(xyz)면 x의 방안만 배척을 거치면 x=f(x)-4-f(xy)-f(xz)+f(xyz)
이 배제 과정은 코드의 dfs 이 배제 과정은 코드의 dfs 이 배제 과정은 코드의 dfs

#include 
using namespace std;
typedef long long ll;
#define int long long
const int maxn=1e5+10;
const int mod=772002;
char st[10][10],a[10][10];
int n,m,pos[1500],x[10],y[10],mou[1500];
ll ans,dp[30][1080]; 
int dx[10]={0,0,1,1,1,-1,-1,-1};
int dy[10]={1,-1,0,1,-1,0,1,-1};
ll DP(int num)
{
	int id=0;
	for(int i=0;i=0&&ny>=0&&nx=n||ny<0||ny>=m )	continue;
		if( a[nx][ny]=='X' )	flag=1;//     ,            
	}
	if( !flag&&a[x][y]!='X' )//       
	{
		a[x][y]='X';
		dfs(step+1,num+1);
		a[x][y]='.';
	}
	dfs(step+1,num);
}
bool check()
{
	for(int i=0;i=0&&nx=0&&ny