博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
dfs深度优先搜索专题02
阅读量:533 次
发布时间:2019-03-09

本文共 5425 字,大约阅读时间需要 18 分钟。

上一个专题在这里:

还是水洼问题,这题特殊的地方在于它只能是方形。
所以我们先对是否存在非方形进行判断,如果非法,直接输出并return掉
然后就都是合法的,转成了水洼问题

#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;typedef long long LL;int n,m;char a[1010][1010];int dx[] = { -1,0,0,1 };int dy[] = { 0,1,-1,0 };bool check(int x, int y) //存在'L'形即为不合法{ int cnt = 0; if (a[x][y] == '#') cnt++; if (a[x+1][y] == '#') cnt++; if (a[x][y+1] == '#') cnt++; if (a[x+1][y+1] == '#') cnt++; if (cnt == 3) return 0; //不合法 else return 1;}void dfs(int x, int y){ a[x][y] = '.'; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&a[nx][ny] == '#') { dfs(nx, ny); } }}int main(){ cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (check(i, j) == 0) { cout << "Bad placement." << endl; return 0; } } } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == '#') { dfs(i, j); ans++; } } } cout << "There are " << ans << " ships." << endl;}

这题的题目我读了好久??

#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;typedef long long LL;int n,m;int a[55]; //每种饲料最小的维他命需求量int b[25][55]; //b[i][j]表示第i包饲料的第j种维他命含量int c[55]; //在搜索过程中存储可行解(存的是选中的饲料的下标)int ans[55]; //存储最小可行解(存的是饲料的下标)int mmin=0x3f3f3f3f;bool check(int x) //判断选中的x种饲料是否满足最小的维他命需求量{ for (int i = 1; i <= n; i++) //遍历判断n种维他命的含量是否满足 { int sum = 0; for (int j = 1; j <= x; j++) { sum += b[c[j]][i]; //计算所有选中的饲料第i种维他命的含量 } if (sum < a[i]) return false; //第i种维他命的含量不够 } return true;//前面所有都没返回false}void dfs(int now, int num) //now表示当前搜索到了第now种饲料,num表示当前选了几种饲料{ if (now > m)//边界,要返回了 { if (check(num)) //判断选中的num种饲料是否满足最小的维他命需求量 { if (num < mmin) //如果num满足且小于之前的最小饲料数 { mmin = num; //更新最小饲料数 for (int i = 1; i <= mmin; i++) { ans[i] = c[i]; //更新答案数组 } } } return; } c[num + 1] = now; //选择的第num种饲料的下标是now dfs(now + 1, num + 1); //要第num个饲料,开始搜索第num+1个 c[num + 1] = 0;//回溯 dfs(now + 1, num);//不要第num个饲料,开始搜索第num+1个}int main(){ cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } cin >> m; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { cin >> b[i][j]; } } dfs(1, 0); cout << mmin << " "; for (int i = 1; i <= mmin; i++) { cout << ans[i] << " "; } cout << endl;}

#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;typedef long long LL;int n,m;int a[11][11];int valid[11][11];int mx = -0x3f3f3f3f;int sum;int dx[] = { -1,-1,-1,0,0,1,1,1 };int dy[] = { 1,0,-1,1,-1,1,0,-1 };void dfs(int x, int y){ if (y == m+1) //当y到边界时,搜索下一行 { dfs(x + 1, 1); return; } if (x == n + 1)//当x到边界时,搜索结束,更新最大值 { mx = max(mx, sum); return; } dfs(x, y + 1); //不取(x,y) if (valid[x][y] == 0) //取(x,y)且(x,y)合法 { sum += a[x][y]; for (int i = 0; i < 8; i++) { ++valid[x + dx[i]][y + dy[i]]; //如果取了(x,y)那么标记和(x,y)相邻的8个点不能再取了——不合法 } dfs(x, y + 1); for (int i = 0; i < 8; i++) //回溯 { --valid[x + dx[i]][y + dy[i]]; } sum -= a[x][y]; }}int main(){ int t; cin >> t; while (t--) { sum = 0; mx = -0x3f3f3f3f; memset(a, 0, sizeof(a)); memset(valid, 0, sizeof(valid)); cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } dfs(1, 1); cout << mx << endl; }}

几个要点

  • 一个单词最多用两次
  • 单词不可以包含:一旦包含了和不用岂不是一样
  • 按照贪心原则,重叠部分应该越少越好
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define IOS ios::sync_with_stdio(false)//#include
using namespace std;typedef long long LL;int n;string s[25];int used[25];int mx = -1;int check(string s, string t) //求s和t重叠部分的长度{ for (int i = 1; i < min(s.size(), t.size()); i++) { int flag = 1; for (int j = 0; j < i; j++) { if (s[s.size() - i + j] != t[j]) flag = 0; } if (flag) return i; } return 0;}void dfs(string str, int len){ mx = max(mx, len); //更新最长的 for (int i = 0; i < n; i++) { if (used[i] >= 2) continue; int c = check(str, s[i]); if (c > 0) { used[i]++; dfs(s[i], len + s[i].size() - c); used[i]--; } }}int main(){ IOS; cin >> n ; for (int i = 0; i <= n; i++) { cin >> s[i]; } dfs(' ' + s[n], 1); //因为check需要重叠部分小于最短长度-1,所以要从前面添加一个无意义充长度的' ' cout << mx << endl;}

找到延伸的方向,按那个方向dfs,用结构体存储路径
来自的思路

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;typedef long long LL;struct node{ int x,y;}c[110];int n;char a[110][110],stand[]="yizhong";int vis[110][110];int dx[] = { -1,-1,-1,0,0,1,1,1 };int dy[] = { 1,0,-1,1,-1,1,0,-1 };int k;void dfs(int x, int y, node c[], int k, int cur){ if (cur == 7) { for (int i = 0; i < 7; i++) { vis[c[i].x][c[i].y] = 1; } } else { int nx = x + dx[k]; int ny = y + dy[k]; if (cur==6||a[nx][ny] == stand[cur + 1]) { c[cur].x = x; c[cur].y = y; dfs(nx, ny, c, k, cur + 1); } }}int main(){ scanf("%d",&n); for (int i = 0; i < n; i++) { scanf("%s", a[i]); } memset(vis, 0, sizeof(vis)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == 'y') { for (int z = 0; z < 8; z++) { int x = i + dx[z]; int y = j + dy[z]; if (a[x][y] == 'i'&&x>=0&&x
=0&&y

转载地址:http://gboiz.baihongyu.com/

你可能感兴趣的文章