DFS入门经典

张开发
• 2026/4/10 23:22:23 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

DFS入门经典
#includeiostream using namespace std; const int N 10; int path[N];//保存序列 int state[N];//数字是否被用过 int n; void dfs(int u) { if(u n)//数字填完了输出 { for(int i 1; i n; i)//输出方案 cout path[i] ; cout endl; } for(int i 1; i n; i)//空位上可以选择的数字为:1 ~ n { if(!state[i])//如果数字 i 没有被用过 { path[u] i;//放入空位 state[i] 1;//数字被用修改状态 dfs(u 1);//填下一个位 state[i] 0;//回溯取出 i } } } int main() { cin n; dfs(1); }#include iostream using namespace std; const int N 11; char q[N][N];//存储棋盘 bool dg[N * 2], udg[N * 2], cor[N];//点对应的两个斜线以及列上是否有皇后 int n; void dfs(int r) { if(r n)//放满了棋盘输出棋盘 { for(int i 0; i n; i) { for(int j 0; j n; j) cout q[i][j]; cout endl; } cout endl; return; } for(int i 0; i n; i)//第 r 行第 i 列 是否放皇后 { if(!cor[i] !dg[i r] !udg[n - i r])//不冲突放皇后 { q[r][i] Q; cor[i] dg[i r] udg[n - i r] 1;//对应的 列 斜线 状态改变 dfs(r 1);//处理下一行 cor[i] dg[i r] udg[n - i r] 0;//恢复现场 q[r][i] .; } } } int main() { cin n; for (int i 0; i n; i ) for (int j 0; j n; j ) q[i][j] .; dfs(0); return 0; }

更多文章