第二十一周代码（java + DFS/BFS）

本文主要是介绍第二十一周代码（java + DFS/BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024/03/04 周一

路径之谜

题目链接

【参考代码】

dfs剪枝

#include <iostream>
#include <vector>
using namespace std;int n;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
bool visit[21][21] = {false};
int north[21], west[21];
vector<int> path;
bool flag = false;void pathAddBlockNumber(int x, int y)
{path.push_back(x * n + y);
}bool check()
{for(int i=0;i<n;i++){if(north[i] != 0 || west[i] != 0)return false;}return true;
}void dfs(int startx, int starty)
{ if(north[starty] < 0 || west[startx] < 0) //剪枝，错误类型return;if(startx == n-1 && starty == n-1 && check()) //结束条件{ //打印路径for(int i=0; i<path.size(); i++){printf("%d ", path[i]);}return;}for(int i=0;i<4;i++){int nowx = startx + dx[i];int nowy = starty + dy[i];if(visit[nowx][nowy] || nowx < 0 || nowx >= n || nowy < 0 || nowy >= n)continue;visit[nowx][nowy] = true;north[nowy]--, west[nowx]--;pathAddBlockNumber(nowx, nowy);dfs(nowx, nowy);visit[nowx][nowy] = false;north[nowy]++, west[nowx]++;path.pop_back();}
}int main()
{scanf("%d", &n);//cin>>n;for(int i=0;i<n;i++){scanf("%d", &north[i]);}for(int i=0;i<n;i++){scanf("%d", &west[i]);}north[0]--,west[0]--; //(0,0)处的计数值先各减1 visit[0][0] = true; //(0,0)已访问 path.push_back(0); //路径加入0这个点dfs(0, 0);return 0;
}

2024/03/05 周二

P1025 [NOIP2001 提高组] 数的划分

题目链接

【参考代码】

#include <iostream>
using namespace std;int count = 0;
int n, k;//后一个数必须大于等于前一个数
void dfs(int nextnumber, int step, int sum)
{if(step == k) //分完step步，都要结束掉{if(sum == n) //符合条件的结果+1count++; return;}//for(int i=nextnumber; i <= (n-sum)/(k-step); i++)for(int i=nextnumber; i <= n-sum; i++){dfs(i, step+1, sum + i);}
}int main()
{cin>>n>>k;dfs(1, 0, 0);cout << count;
}