X02day6题解(我是来透题的bro)
2024-08-06 16:24:12
发布于：广东
10阅读
0回复
0点赞
我是来捣乱的!!
X02:
X02_D6B_深度优先搜索
day6有手就行
其实用广搜的代码一样der
献上框架
#include<bits/stdc++.h>
using namespace std;
int main(){
return 0;
}
我好多都是用广搜做的,所以先讲一下深搜:
深搜常常指利用递归函数方便地实现暴力枚举的算法，与图论中的 DFS 算法有一定相似之处，但并不完全相同。
模版,启动!!!!
int m, arr[103]; // arr 用于记录方案
void dfs(int n, int i, int a) {
if (n == 0) {
for (int j = 1; j <= i - 1; ++j) {
printf("%d ", arr[j]);
}
printf("\n");
}
if (i <= m) {
for (int j = a; j <= n; ++j) {
arr[i] = j;
dfs(n - j, i + 1, j);
}
}
}
// 主函数
scanf("%d%d", &n, &m);
dfs(n, 1, 1);
大家也可以在oi-wiki.org上看到
上代码
T19368.邻居
#include<bits/stdc++.h>
using namespace std;
constexpr int dirs[][2] {0,1,1,0,0,-1,-1,0};
int main(){
int n,m,x,y;
cin>>n>>m>>x>>y;
for(auto&[dx,dy] : dirs){
int nx=x+dx,ny=y+dy;
if(nx<1||nx>n||ny<1||ny>m){
cout<<"NA\n";
}
else{
cout<<nx<<" "<<ny<<endl;
}
}
return 0;
}
T19371.逃离迷宫
#include <bits/stdc++.h>
using namespace std;
constexpr int dirs[][2]{0,1,1,0,0,-1,-1,0};
constexpr int N=40;
int n,m,vis[N][N];
vector<string> mat;
void dfs(int x,int y){
vis[x][y]=1;
for(auto &[dx,dy]:dirs){
int nx=x+dx,ny=y+dy;
if(nx<0||nx>=n||ny<0||ny>=m) continue;
if(vis[nx][ny]||mat[nx][ny]=='#') continue;
dfs(nx,ny);
}
}
using namespace std;
int main(){
cin>>n>>m;
mat = vector<string>(n);
for(auto&s:mat) cin>>s;
dfs(0,0);
cout<<(vis[n-1][m-1]? "YES":"NO")<<endl;
return 0;
}
T19372.逃离迷宫2
#include <bits/stdc++.h>
using namespace std;
const int dirs[][2]={0,1,1,0,0,-1,-1,0};
const int INF=100;
int n,m;
vector<string>mat;
//从x,y出发到终点的最小步数
int dfs(int x,int y)
{
if(x==n-1 and y==m-1){
return 0;
}
mat[x][y]='#';
int step=INF;
for(int i=0;i<4;++i)
{
int nx=x+dirs[i][0];
int ny=y+dirs[i][1];
if(nx<0 or nx>=n or ny<0 or ny>=m) continue;
if(mat[nx][ny]=='#') continue;
step=min(step,dfs(nx,ny)+1);
}
mat[x][y]='.';
return step;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
mat=vector<string>(n);
for(int i=0;i<n;++i)
{
cin>>mat[i];
}
int res=dfs(0,0);
if(res<INF) cout<<res;
else cout<<"-1";
return 0;
}
T19373.细胞
#include<bits/stdc++.h>
using namespace std;
int n,m;
char mat[1010][1010];
int cnt=0;
const int dirx[]={-1,1,0,0};
const int diry[]={0,0,-1,1};
void dfs(int x,int y){
mat[x][y]='0';
for(int i=0;i<4;i++){
int nx=x+dirx[i];
int ny=y+diry[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mat[nx][ny]=='1'){
if (mat[nx][ny] == '1') {
dfs(nx, ny);
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mat[i][j];
if(mat[i][j]!='0')mat[i][j]='1';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mat[i][j]=='1'){
dfs(i,j);
cnt++;
}
}
}
cout<<cnt;
return 0;
}
T19369.全排列
#include<bits/stdc++.h>
using namespace std;
constexpr int N=10;
int n,a[N] = {0};
bool vis[200] = {0};
void dfs(int x){
if(x == n+1){
for(int i = 1;i<=n;i++){
cout<<a[i]<<' ';
}
cout<<endl;
return;
}
for(int i = 1;i<=n;i++){
if(!vis[i]){
a[x] = i;
vis[i] = 1;
dfs(x+1);
vis[i] = 0;
}
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}
T19498.选数
#include<bits/stdc++.h>
using namespace std;
constexpr int N=20;
int n, k,ans,a[N]{0};
bool ikun(int num){
if(num<2) return 0;
for(int i=2;i*i<=num;i++){
if(num%i==0) return 0;
}
return 1;
}
int xuanshu(int i, int num, int sum){
if(num == 0){
if(ikun(sum)) ans++;
return 0;
}
if(n-i+1<num){
return 0;
}
int cnt;
for(cnt=i; cnt<=n; cnt++){
xuanshu(cnt+1, num-1, sum+a[cnt]);
}
return 0;
}
int main(){
scanf("%d %d", &n, &k);
int i;
for(i=1;i<=n;i++){
scanf("%d", &a[i]);
}
xuanshu(1,k,0);
printf("%d", ans);
return 0;
}
T20407.数量
#include <iostream>
using namespace std;
bool a[10][10],b[10][10]={0};
int n,m,t,nx,ny,sx,sy,ans=0;
const int ikun[4]={0,0,1,-1};
const int kun[4]={-1,1,0,0};
void dfs(int x,int y)
{
if(x<1||y<1||x>n||y>m)
return;
if(x==sx&&y==sy)
{
ans++;
return;
}
b[x][y]=1;
for(int i=0;i<=3;i++)
if(b[x+ikun[i]][y+kun[i]]==0&&a[x+ikun[i]][y+kun[i]]==true)
dfs(x+ikun[i],y+kun[i]);
b[x][y]=0;
}
int main()
{
int tx,ty;
cin>>n>>m>>t>>nx>>ny>>sx>>sy;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=1;
for(int i=1;i<=t;i++)
{
cin>>tx>>ty;
a[tx][ty]=0;
}
b[nx][ny]=1;
dfs(nx,ny);
cout<<ans;
return 0;
}
结束啦!!!
这里空空如也
有帮助，赞一个