1.水洼数目 题目
有一个大小为 NM 的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出 园子里总共有多少水洼？（八连通指的是下图中相对 W 的的部分） *** *W* *** 限制条件 N, M ≤ 100 样例: 输入 N=10, M=12 园子如下图（'W’表示积水， '.'表示没有积水） 10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W. 输出 3思路
存一下地图，找到水洼直接向八个方向搜索 进入dfs就可把当前点标记为搜索过或者直接把地图中的当前点的水洼去掉题解
#include<iostream> using namespace std; int n,m; int cnt; char mp[101][101]; bool vis[101][101]; int dir[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; void dfs(int x,int y){ mp[x][y] = '.'; for(int i = 0;i<7;i++){ int tx = x + dir[i][0]; int ty = y + dir[i][1]; if(tx >= 0 && ty >= 0 && tx <n && ty < m && mp[tx][ty] == 'W'){ dfs(tx,ty); } } } int main(){ cin >>n>>m; for(int i = 0;i<n;i++){ cin >>mp[i]; } for(int i = 0;i<n;i++){ for(int j = 0;j<m;j++){ if(mp[i][j] == 'W'){ dfs(i,j); cnt++; } } } cout <<cnt<<endl; return 0; }2 八皇后 题目
八皇后问题是以国际象棋为背景的问题：有八个皇后（可以当成八个棋子） 如何在 8*8 的棋盘中放置八个皇后，使得任意两个皇后都不在同一条横线、纵线或者斜线上。思路
dfs传入行数，按行遍历即可题解
#include<iostream> using namespace std; bool vis[12]; bool x1[20],x2[20]; int ans; bool check(int r,int i){ return !vis[i] && !x1[r+i] && !x2[r-i+8]; } void dfs(int r){ if(r == 8){ ans++; return; } for(int i = 0;i<8;i++){ if(check(r,i)){ vis[i] = x2[r-i+8] = x1[r+i] = true; dfs(r+1); vis[i] = x2[r-i+8] = x1[r+i] = false; } } } int main(){ dfs(0); cout <<ans<<endl; return 0; }3 n皇后 题目
题目描述： 给定一个 n∗n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。 输入格式 输入的第一行为一个整数 n，表示棋盘的大小。 接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。 输出格式 输出一个整数，表示总共有多少种放法。 样例输入1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 样例输出1 2 样例输入2 4 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 样例输出2 0思路
和八皇后不同的就是需要先考虑一个黑皇后，在考虑另一个 其他思路和八皇后基本相同题解
#include<iostream> #include<cstdio> using namespace std; int n,ans; int mp[10][10]; int vx[10],vy[10],vd1[20],vd2[20]; void dfs(int x,int p){ if(x == n && p == 2){ ans++; return; } if(x == n){ dfs(0,p+1); } for(int i = 0;i<n;i++){ if(mp[x][i] && (vy[i] != 3 &&vy[i] != p && vd1[x+i] != 3&& vd1[x+i] != p && vd2[x-i+n] != 3 &&vd2[x-i+n] != p)){ mp[x][i] = 0; vy[i] += p; vd1[x+i] += p; vd2[x-i+n] += p; dfs(x+1,p); mp[x][i] = 1; vy[i] -= p; vd1[x+i] -= p; vd2[x-i+n] -= p; } } } int main(){ scanf("%d",&n); for(int i = 0;i<n;i++){ for(int j = 0;j<n;j++){ scanf("%d",&mp[i][j]); } } dfs(0,1); cout <<ans<<endl; return 0; }