八皇后代码 来自 https://www.bilibili.com/video/av21776496?from=search&seid=14795429927506117804
迷宫寻路自己写的
迷宫寻路 (1 为障碍, 2 为路)
- #define _CRT_SECURE_NO_WARNINGS
- #include<stdio.h>
- #include<stdlib.h>
- #define N 1234
- int n, m, count = 0;
- int map[N][N];
- int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
- typedef struct Nodes
- {
- int x;
- int y;
- }st; st way[N];
- void out()
- {
- printf("(0,0)->");
- for (int i = 0; i <count - 1; i++)
- {
- printf("(%d,%d)->", way[i].x, way[i].y);
- }
- printf("(%d,%d)\n", way[count - 1].x, way[count - 1].y);
- }
- void DFS(int a, int b)
- {
- if (a == m - 1 && b == n - 1)
- {
- out();
- return;
- }
- for (int i = 0; i <4; i++)
- {
- if (a + dx[i] < 0 || b + dy[i] < 0 || a + dx[i]>= m || b + dy[i]>= n)
- continue;
- if (map[a + dx[i]][b + dy[i]] == 0)
- {
- map[a][b] = 1;
- way[count].x = a + dx[i];
- way[count++].y = b + dy[i];
- DFS(a + dx[i], b + dy[i]);
- count--;
- map[a][b] = 0;
- }
- }
- }
- // 入口是 map[0][0], 出口是 map[m-1][n-1]
- int main(void)
- {
- scanf("%d%d", &m, &n);
- for (int i = 0; i <m; i++)
- {
- for (int j = 0; j < n; j++)
- {
- scanf("%d", &map[i][j]);
- }
- }
- DFS(0, 0);
- system("pause");
- return 0;
- }
- /*
- 测试数据
- 第一组
- 6 5
- 0 0 1 1 1
- 0 0 0 0 1
- 1 0 1 0 1
- 1 0 1 0 1
- 1 1 1 0 1
- 1 0 1 0 0
- 结果
- (0,0)->(0,1)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)
- (0,0)->(1,0)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)
- 第二组
- 6 5
- 0 0 1 1 1
- 0 0 0 0 1
- 1 0 1 0 1
- 1 0 1 0 1
- 1 0 1 0 1
- 1 0 0 0 0
- 结果
- (0,0)->(0,1)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)
- (0,0)->(0,1)->(1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
- (0,0)->(1,0)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)
- (0,0)->(1,0)->(1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
- */
- View Code
八皇后
- #define _CRT_SECURE_NO_WARNINGS
- #include<stdio.h>
- #include<stdlib.h>
- int map[10];
- int visl[10];
- void out()
- {
- for (int i = 1; i <8; i++)
- {
- for (int j = i + 1; j <= 8; j++)
- {
- if (i - j == map[i] - map[j] || i - j == map[j] - map[i]) // 斜线
- return;
- }
- }
- for (int i = 1; i <= 8; i++)
- {
- printf("(%d , %d)", i, map[i]);
- }puts("");
- }
- void dfs(int num)
- {
- if (num>= 9)
- {
- out();
- return;
- }
- for (int i = 1; i <= 8; i++)
- {
- if (visl[i] == 0)
- {
- visl[i] = 1;
- map[num] = i;
- dfs(num + 1);
- visl[i] = 0;
- }
- }
- }
- int main(void)
- {
- dfs(1);
- system("pause");
- return 0;
- }
- View Code
就将这两题作为模板吧.
两者都是需要记录所有路径, 在根据结束条件判断是否输出
所以这种模板的功能是:
1 记录所有路径
2 可以根据结束条件, 选择你所需要的路径
============================================
梦想是注定孤独的旅行, 路上少不了质疑和嘲笑, 但那又怎样, 哪怕遍体鳞伤, 也要活的漂亮
来源: http://www.bubuko.com/infodetail-3460714.html