http://acm.hdu.edu.cn/showproblem.php?pid=1045
暴力搜索解决,只是一点不明白,在更新max值时如果我return了竟然错了,没有return就ac了。
#include <stdio.h> #include <string.h> char map[6][6]; bool used[6][6]; int n, wall; int max; void dfs(int curs, int curt) { int i, j, k, m, s = 0; bool use[6][6]; if(curs = n*n - wall){ if(curt > max)max = curt; } for(i = 0; i < n; i ++){ for(j = 0; j < n; j ++){ if(map[i][j] == '.' && !used[i][j]){ used[i][j] = true; s ++; for(k = 0; k < n; k ++){ for(m = 0; m < n; m ++){ use[k][m] = used[k][m]; } } for(k = j + 1; k < n; k ++){ if(map[i][k] == 'X')break; if(!used[i][k]){ used[i][k] = true; s ++; } } for(k = j - 1; k >= 0; k --){ if(map[i][k] == 'X')break; if(!used[i][k]){ used[i][k] = true; s ++; } } for(k = i + 1; k < n; k ++){ if(map[k][j] == 'X')break; if(!used[k][j]){ used[k][j] = true; s ++; } } for(k = i - 1; k >= 0; k --){ if(map[k][j] == 'X')break; if(!used[k][j]){ used[k][j] = true; s ++; } } dfs(curs + s, curt + 1); for(k = 0; k < n; k ++){ for(m = 0; m < n; m ++){ used[k][m] = use[k][m]; } } used[i][j] = false; } } } } int main() { // freopen("input.txt", "r", stdin); int i, j; while(scanf("%d", &n), n){ for(i = 0; i < n; i ++){ scanf("%s", map[i]); } wall = 0; for(i = 0; i < n; i ++){ for(j = 0; j < n; j ++){ if(map[i][j] == 'X')wall ++; } } max = 0; memset(used, false, sizeof(used)); dfs(0, 0); printf("%d\n", max); } return 0; }