AOJ0548 Reindeer with no sense of direction
全探索系苦手なので放置していたが本選前なのでやってみた。
教会から逆向きに探して、使ってない家があったら必ず配るをすると良いことに気付くだけ。
TL緩いしあんまり工夫していない....
#include <cstdio> #include <cstring> using namespace std; #define rep(i, n) for(int i = 0; i < (int)n; ++i) int m, n; int cnt, sx, sy; int f[20][20]; bool vis[20][20]; int dfs(int x, int y, int r){ int ret = 0; if(r == 0){ if(x == sx || y == sy) return 1; else return 0; } for(int nx = x - 1; nx >= 0; --nx){ if((f[y][nx] & 1) && !vis[y][nx]){ vis[y][nx] = true; ret += dfs(nx, y, r - 1); vis[y][nx] = false; break; } } for(int nx = x + 1; nx < m; ++nx){ if((f[y][nx] & 1) && !vis[y][nx]){ vis[y][nx] = true; ret += dfs(nx, y, r - 1); vis[y][nx] = false; break; } } for(int ny = y - 1; ny >= 0; --ny){ if((f[ny][x] & 1) && !vis[ny][x]){ vis[ny][x] = true; ret += dfs(x, ny, r - 1); vis[ny][x] = false; break; } } for(int ny = y + 1; ny < n; ++ny){ if((f[ny][x] & 1) && !vis[ny][x]){ vis[ny][x] = true; ret += dfs(x, ny, r - 1); vis[ny][x] = false; break; } } return ret; } int main(){ while (scanf("%d %d", &m, &n), m || n){ cnt = 0; rep(i, n){ rep(j, m){ scanf("%d", &f[i][j]); if(f[i][j] == 2){ sx = j; sy = i; f[i][j] = 0; }else if(f[i][j] & 1) cnt++; } } printf("%d\n", dfs(sx, sy, cnt)); } return 0; }