POJ3050--Hopscotch
3592 ワード
任意の点から出発して、4つの方向に歩くことができて、繰り返して歩くことができて、6回歩くことができます.何種類の異なる配列が得られるか.分析:テーマデータは強くないようです.暴力DFSで過ごせる.
コード:
コード:
#include <cstdio>
using namespace std;
int a[6][6], c[100000], ans, cnt, flag;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void dfs(int x, int y, int t) {
if(cnt == 6) {
flag = 1;
for(int i = 0; i < ans; i++) {
if(t == c[i]) {
flag = 0;
break;
}
}
if(flag)
c[ans++] = t;
return;
}
for(int i = 0; i < 4; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if(tx >= 0 && tx < 5 && ty >= 0 && ty < 5) {
cnt++;
dfs(tx, ty, t * 10 + a[tx][ty]);
cnt--;
}
}
}
int main() {
for(int i = 0; i < 5; i++)
for(int j = 0; j < 5 ;j++)
scanf("%d", &a[i][j]);
cnt = 0;
ans = 0;
for(int i = 0; i < 5; i++)
for(int j = 0; j < 5; j++)
dfs(i, j, 0);
printf("%d
", ans);
return 0;
}