grid pku 2754 n后问题

﹏ヽ暗。殇╰゛Y 2022-08-13 05:29 90阅读 0赞

//DFS递归解 #include #include using namespace std; int record[93][9]; int x[9]; int index; bool OK(int col, int line) { for(int i = 1; i < line; ++i) if(abs(i - line) == abs(x[i]- col) || x[i] == col) return false; return true; } void DFS(int line) { if(line > 8) { index++; for(int i = 1;i <= 8; ++i) record[index][i] = x[i]; } else { for(int col = 1; col <= 8; ++col) { if(OK(col, line)) { x[line] = i; DFS(line+1); } } } } //回溯法栈解 int main() { DFS(1); int n; scanf(“%d”, &n); while(n—) { int order; scanf(“%d”, &order); for(int i = 1; i <= 8; ++i) printf(“%d”, record[order][i]); printf(“/n”); } return 0; } #include #include using namespace std; int record[93][9]; int s[9]; int index; bool OK(int line) { for(int i = 1; i < line; ++i) if(abs(i - line) == abs(s[i] - s[line]) || s[line] == s[i]) return false; return true; } void backTrack(int line) { for(int i= 1;i <= 8; ++i) s[i] = 0; int top = 1; while(top != 0) { s[top]++; while(s[top] <= 8 && !OK(top)) s[top]++; if(s[top] > 8) { s[top] = 0; —top; } else // s[top] <= 8 { if(top == 8) { index++; for(int i = 1;i <= 8; ++i) record[index][i] = s[i]; } else top++; } } } int main() { backTrack(1); int n; scanf(“%d”, &n); while(n—) { int order; scanf(“%d”, &order); for(int i = 1; i <= 8; ++i) printf(“%d”, record[order][i]); printf(“/n”); } return 0; }

发表评论

表情：
评论列表 （有 0 条评论，90人围观）

还没有评论，来说两句吧...

相关阅读

    相关 n后问题

    n后问题 一、 问题描述 在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，请输出皇后的位置

    ﹏ヽ暗。殇╰゛Y﹏ヽ暗。殇╰゛Y/ 0 赞/ 104 阅读

    相关 n后问题(回溯法)

    一.问题描述: 在n\n格子上放置n个皇后, 按照国际象棋规矩不可让皇后相互攻击, 即如何两个皇后不放在同一列同一行同一斜线上. 二.算法设计: 将问题转化为逐行放置皇后

    末蓝、末蓝、/ 0 赞/ 254 阅读