uva211
题意：https://vjudge.net/problem/UVA-211
思路
每一个方块都只有两种方式，横着和竖着如果到了可以换行的时候，上一行还没有摆满，则不通过，回溯注意格式，特别麻烦
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std
;
int mp
[10][10];
int ans
[10][10];
bool vis
[10][10];
int domino
[7][7];
bool used
[30];
int ansNum
= 0;
void init()
{
memset(domino
, 0, sizeof(domino
));
memset(used
, 0, sizeof(used
));
int a
= 1;
for (int i
= 0; i
<= 6; i
++)
{
for (int j
= i
; j
<= 6; j
++)
{
domino
[i
][j
] = a
++;
}
}
}
bool getLine(int n
)
{
int a
;
if (scanf("%d", &a
) == EOF)
return false;
mp
[n
][0] = a
;
for (int i
= 1; i
< 8; i
++)
scanf("%d", &mp
[n
][i
]);
return true;
}
void putAns()
{
ansNum
++;
printf("\n\n");
for (int i
= 0; i
< 7; i
++)
{
for (int j
= 0; j
< 8; j
++)
{
printf("%4d", ans
[i
][j
]);
}
printf("\n");
}
}
int dx
[] = {0, 1};
int dy
[] = {1, 0};
bool check(int r
)
{
for (int i
= 0; i
< 8; i
++)
{
if (ans
[r
][i
] == 0)
return false;
}
return true;
}
void solve(int r
, int c
)
{
if (r
== 7)
{
putAns();
return;
}
if (c
== 8 && !check(r
))
return;
if (c
== 8)
{
solve(r
+1,0);
return;
}
if (ans
[r
][c
])
solve(r
, c
+ 1);
else
{
for (int i
= 0; i
< 2; i
++)
{
if (ans
[r
+ dx
[i
]][c
+ dy
[i
]])
continue;
int a
= mp
[r
][c
], b
= mp
[r
+ dx
[i
]][c
+ dy
[i
]];
if (a
> b
)
swap(a
, b
);
if (used
[domino
[a
][b
]])
continue;
used
[domino
[a
][b
]] = 1;
ans
[r
][c
] = ans
[r
+ dx
[i
]][c
+ dy
[i
]] = domino
[a
][b
];
solve(r
, c
+ 1);
used
[domino
[a
][b
]] = 0;
ans
[r
][c
] = ans
[r
+ dx
[i
]][c
+ dy
[i
]] = 0;
}
}
}
int main()
{
int kase
= 0;
init();
while (getLine(0))
{
if (kase
!= 0)
printf("\n\n\n\n\n");
for (int i
= 1; i
< 7; i
++)
getLine(i
);
printf("Layout #%d:\n\n\n", ++kase
);
for (int i
= 0; i
< 7; i
++)
{
for (int j
= 0; j
< 8; j
++)
printf("%4d", mp
[i
][j
]);
printf("\n");
}
printf("\nMaps resulting from layout #%d are:\n", kase
);
memset(ans
, 0, sizeof(ans
));
ansNum
= 0;
solve(0, 0);
printf("\n\nThere are %d solution(s) for layout #%d.\n", ansNum
, kase
);
}
return 0;
}
