bzoj 3109
直接DFS就行，这题比较麻烦，打了一下午，不过幸好也没有什么错，跑了2860ms，还算不错。注意一下行末空格是不允许存在的
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int hang_rl[20][20], lie_rl[20][20], mp[20][20], hang_used[20][20], lie_used[20][20], gong_used[20][20];
char getch() {
char x = getchar();
while (x != 'v' && x != '<' && x != '>' && x != '^') x = getchar();
return x;
}
int getGongByPos(int x, int y) {
if (x <= 3) {//the 1st row
if (y <= 3) return 1;
if (y <= 6) return 2;
return 3;
} else if (x <= 6) {//the 2nd row
if (y <= 3) return 4;
if (y <= 6) return 5;
return 6;
} else {//the 3rd row
if (y <= 3) return 7;
if (y <= 6) return 8;
return 9;
}
return -1;
}
void inputHang(int h) {
for (int i=0;i<3;i++) {
char c1 = getch(), c2 = getch();
hang_rl[h][i * 3 + 1] = (c1 == '<' ? 0 : 1);
hang_rl[h][i * 3 + 2] = (c2 == '<' ? 0 : 1);
}
}
void inputLie(int l) {
for (int i=0;i<3;i++) {
char c1 = getch(), c2 = getch(), c3 = getch();
lie_rl[l][i * 3 + 1] = (c1 == 'v' ? 0 : 1);
lie_rl[l][i * 3 + 2] = (c2 == 'v' ? 0 : 1);
lie_rl[l][i * 3 + 3] = (c3 == 'v' ? 0 : 1);
}
}
void dfs(int h, int l) {
if (h == 10) {
for (int i=1;i<=9;i++) {
for (int j=1;j<=9;j++) {
printf("%d", mp[i][j]);
if (j != 9) putchar(' ');
}
putchar('\n');
}
exit(0);
}
int gong = getGongByPos(h, l);
for (int i=1;i<=9;i++) {
if (hang_used[h][i] || lie_used[l][i] || gong_used[gong][i]) continue;
if (lie_rl[h - 1][l] == 1) if (i <= mp[h - 1][l]) continue;
if (lie_rl[h - 1][l] == 0) if (i > mp[h - 1][l]) continue;
if (hang_rl[h][l - 1] == 1) if (i > mp[h][l - 1]) continue;
if (hang_rl[h][l - 1] == 0) if (i <= mp[h][l - 1]) continue;
mp[h][l] = i, hang_used[h][i] = lie_used[l][i] = gong_used[gong][i] = true;
if (l + 1 > 9) dfs(h + 1, 1); else dfs(h, l + 1);
mp[h][l] = 0, hang_used[h][i] = lie_used[l][i] = gong_used[gong][i] = false;
}
}
void clean() {
ms(hang_rl, -1), ms(lie_rl, -1), ms(mp, 0), ms(hang_used, false), ms(lie_used, false), ms(gong_used, false);
}
void solve() {
clean();
int h = 0, l = 0;
for (int i=1;i<=3;i++) {
inputHang(++h);
inputLie(++l);
inputHang(++h);
inputLie(++l);
inputHang(++h);
l++;
}
dfs(1, 1);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
solve();
return 0;
}
