読者です 読者をやめる 読者になる 読者になる

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;
}