网络创作网站,html网页制作个人主页制作教程,织梦网站栏目设计,百度视频免费下载深度优先搜索#xff08;DFS#xff09;
求连通块 #x1f449;HDOJ-1241 Oil Deposits
【题目】石油勘探公司把油田分成许多的大格#xff0c;每个大格又分为许多小格#xff0c;然后分析各个小格是否有石油矿藏。有矿藏的小格#xff08;用表示#xff09;称为容器.…深度优先搜索DFS
求连通块 HDOJ-1241 Oil Deposits
【题目】石油勘探公司把油田分成许多的大格每个大格又分为许多小格然后分析各个小格是否有石油矿藏。有矿藏的小格用表示称为容器. 如果2个容器相连横、竖、斜, 则它们是同一矿区的不同部分。输入各大格的矿藏分布无矿藏用*表示输出其中有多少个不同的矿区。
#includeiostream
using namespace std;
char g[105][105]{0};
int m,n;
int dir[8][2]{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
void dfs(int x,int y){if(x0||xm||y0||yn||g[x][y]*) return;//越界或走过则返回g[x][y]*;//标记走过for(int k0;k8;k)//查找下一级可用点dfs(xdir[k][0],ydir[k][1]);
}
int main(){ while(cinmnm){//m行n列int i,j;for(i0;im;i)//建议从0开始便于整行输入cing[i];int num0;for(i0;im;i)for(j0;jn;j)if(g[i][j])//仅在第一级递归计数故分离{num;dfs(i,j);}coutnumendl;}return 0;
}HDOJ-1031 N皇后问题
【题目】在N×N的方格棋盘放置了N个皇后使得它们不相互攻击即任意2个皇后不允许处在同一排同一列也不允许处在与棋盘边框成45角的斜线上。输入给定的NN≤10输出有多少种合法的放置方法。
【思路】在N×N棋盘中摆N个皇后意味着每行有一个皇后每列有一个皇后每条主对角线有一个皇后每条副对角线有一个皇后换言之每个皇后控制着一行、一列。一条主对角线、一条副对角线。因此以每行对应一次循环用a,b,c三个数组存储各主对角线、副对角线、列的占用情况。点(x,y)位于第x行第y列第y-xn条主对角线(1-ny-xn-1处理使数组从1开始)第xy条副对角线(2xy2n)。
#includeiostream
#includecstring
using namespace std;
int n,so;
bool a[25],b[15],c[25];//a代表主对角线b代表列c代表副对角线
void dfs(int i){if(in) {so;return;}for(int j1;jn;j){//每列if(a[j-in]||b[j]||c[ij]) continue;//不可用则跳过a[j-in]true;b[j]true;c[ij]true;//标记控制区域dfs(i1);//查找下一行可用点a[j-in]false;b[j]false;c[ij]false;//取消标记}
}
int main(){int ans[15]{0};for(n1;n10;n){memset(a,false,sizeof(a));memset(b,false,sizeof(b));memset(c,false,sizeof(c)); so0;dfs(1);ans[n]so;}while(cinnn)coutans[n]endl;return 0;
}HDOJ-1426 Sudoku Killer
【题目】输入一批不完整的数独地图未知数值用?表示输出它们的解。对于每组测试数据保证它有且只有一个解
【思路】 仔细分析发现与上一题有类似之处小格中的每一个数字x都可以看做是所在行、列、九宫格的数字x的控制数字——这个数字控制着所在行、列、九宫格在其控制区域内不能出现另一个x。用结构体存储空格的位置i0~8代表小格行标j0~8代表小格列标则i/3代表九宫格行标j/3代表九宫格列标。以每个空格对应一层递归用a,b,c三个数组存储各行、列、九宫格的可用性数组最后一维代表9个可能的数字其他维度代表序号。 由题意每个空格的值不全为9。当从最后一个空格已填写出发进行下一层递归时触发条件空格溢出记录填写完成函数返回到倒数第二个空格的下一次循环。填写完成条件满足循环变量的上一个值填写到真正的数独空格中函数再返回到倒数第三个空格……对于值为9的情况在循环之外另行处理。 用两层循环读入数独地图存到字符数组中读入的字符若是数字标记控制区域若是空格记录其位置坐标。
#includeiostream
#includecstring
#includecstdio
using namespace std;
char map[9][9];
struct space{int i;int j;}s[81];
bool a[9][12],b[9][12],c[3][3][12];//a代表行b代表列c代表九宫格
int sn,snm;//snSpace Number空格编号,snm空格编号最大值
int done;//done为1代表所有空格填写完成
void dfs(int sn){if(snsnm) {done1;return;}int v;for(v1;v9;v){//每个可能值if(done1) {map[s[sn].i][s[sn].j]0v-1;break;}if(a[s[sn].i][v]||b[s[sn].j][v]||c[s[sn].i/3][s[sn].j/3][v]) continue;//不可用则跳过a[s[sn].i][v]true;b[s[sn].j][v]true;c[s[sn].i/3][s[sn].j/3][v]true;//标记控制区域dfs(sn1);//填写下一个空格a[s[sn].i][v]false;b[s[sn].j][v]false;c[s[sn].i/3][s[sn].j/3][v]false;//取消标记}if(v10done1) map[s[sn].i][s[sn].j]0v-1;
}
int main(){char ch;int f1;do{int i,j;memset(a,false,sizeof(a));memset(b,false,sizeof(b));memset(c,false,sizeof(c));done0;sn0;for(i0;i9;i){for(j0;j9;j){cinch;if(ch!?) {a[i][ch-0]true;b[j][ch-0]true;c[i/3][j/3][ch-0]true;}else {s[sn].ii;s[sn].jj;sn;}map[i][j]ch;}}snmsn-1;dfs(0);if(f0) coutendl; else f0;//第二组数据开始输出前加一空行for(i0;i9;i){for(j0;j8;j)coutmap[i][j] ;coutmap[i][j]endl; } }while(scanf(%c,ch)!EOF);return 0;
}【总结】1031 之前以单个方格作为区域可用性的存储单元这样一个方格可能被多个皇后控制故不能用bool标记而是放上一个皇后将其占用区域与控制区域值加1取消标记时将皇后将其占用区域与控制区域值减1。在处理射线扩展时方向数组与越界判断繁复放弃。参考他人之后发现利用棋盘长宽等长的条件可以简化问题。
记忆化搜索
【题目】 ○题目描述 在一个数阵中求出最长的严格下降路径的长度只能向相邻的上下左右走 如在下面这个数阵中最长的路径为25-24-23…-1(长度为25) 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 ○输入 第一行包含测试用例数T。每个测试用例第1行是名称字符串、行数r和列数c。之后是r行每行有c个数。N和r和c不大于100; ○输出 对于每个测试用例打印一行其中包含区域名称、冒号、空格和最长长度。 ○样例输入 1 scj 10 5 56 14 51 58 88 26 94 24 39 41 24 16 8 51 51 76 72 77 43 10 38 50 59 84 81 5 23 37 71 77 96 10 93 53 82 94 15 96 69 9 74 0 62 38 96 37 54 55 82 38 ○样例输出 scj: 7
【思路】 dp[i][j]存储从a[i][j]开始的最长路径长度则dp[i][j]1max(dp[x][y]) 点(x,y)与(i,j)相邻且不越界且满足a[i][j]a[x][y]若不存在这样的点max值为0 递推需要遵循线性顺序而本题涉及路径故使用记忆化搜索。记忆化搜索涉及递归原因是搜索过程中调用的结果可能尚未生成需要针对调用对象展开进一层搜索。 用一个函数来生成dp[i][j]的值函数执行过程中会更新从(i,j)出发的所有路径上的点的dp值但路径不一定包含所有点。在遍历所有点之后 a n s max 1 ≤ i ≤ r , 1 ≤ j ≤ c d p [ i ] [ j ] ans\max_{1≤i≤r,1≤j≤c} dp[i][j] ans1≤i≤r,1≤j≤cmaxdp[i][j]
#includequeue
#includealgorithm
#includeiostream
#includecstdio
#includecstring
using namespace std;
int r, c;
int a[105][105];
int dp[105][105];
int search(int n, int m){int temp a[n][m];if(n - 1 0 a[n-1][m] temp) {if(dp[n-1][m] ! 0) dp[n][m] max(dp[n][m], dp[n-1][m] 1);else dp[n][m] max(dp[n][m], search(n-1, m) 1);}if(n 1 r a[n1][m] temp) {if(dp[n1][m] ! 0) dp[n][m] max(dp[n][m], dp[n1][m] 1);else dp[n][m] max(dp[n][m], search(n1, m) 1);}if(m - 1 0 a[n][m-1] temp) {if(dp[n][m-1] ! 0) dp[n][m] max(dp[n][m], dp[n][m-1] 1);else dp[n][m] max(dp[n][m], search(n, m-1) 1);}if(m 1 c a[n][m1] temp) {if(dp[n][m1] ! 0) dp[n][m] max(dp[n][m], dp[n][m1] 1);else dp[n][m] max(dp[n][m], search(n, m1) 1);}return dp[n][m];
}int main() {int t;scanf(%d, t);while(t--){memset(dp, 0, sizeof(dp));char ch[105];scanf(%s, ch);scanf(%d %d, r, c);for(int i 1; i r; i) for(int j 1; j c; j) scanf(%d, a[i][j]);int maxmum 0;for(int i 1; i r; i) for(int j 1; j c; j)maxmum max(maxmum, search(i, j));printf(%s: , ch);printf(%d\n, maxmum 1);}return 0;
}