首页 > 其他分享 >001DFS深搜

001DFS深搜

时间:2024-08-12 17:06:53浏览次数:4  
标签:20 int back nx ny maxn 001DFS

洛谷练习

1)路径之谜

代码(未调
#include <bits/stdc++.h>
using namespace std;

int n;
const int maxn = 25;
int maxa[maxn];
int maxb[maxn];
int nowa[maxn];
int nowb[maxn];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int mp[maxn][maxn];
vector<int> xx, yy;
bool st[maxn][maxn];
bool flag;

bool check() {
    for (int i = 1; i <= n; i++) {
        if (nowa[i] != maxa[i] || nowb[i] != maxb[i])
            return false;
    }
    return true;
}

void dfs(int x, int y) {
    if (flag) return;
    if (x == n && y == n && check()) {
        for (int i = 0; i < xx.size(); i++) {
            cout << mp[xx[i]][yy[i]] << " ";
        }
        flag = true;
        return;
    }

    for (int i = 0; i < 4; i++) {
        int a = x + dx[i];
        int b = y + dy[i];

        if (a < 1 || b < 1 || a > n || b > n) continue;
        if (nowa[a] >= maxa[a] || nowb[b] >= maxb[b]) continue;
        if (st[a][b]) continue;

        nowa[a]++;
        nowb[b]++;
        st[a][b] = true;
        xx.push_back(a);
        yy.push_back(b);
        dfs(a, b);
        nowa[a]--;
        nowb[b]--;
        st[a][b] = false;
        xx.pop_back();
        yy.pop_back();
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> maxa[i];
    for (int i = 1; i <= n; i++)
        cin >> maxb[i];

    int t = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            mp[i][j] = t++;
    }

    xx.push_back(1);
    yy.push_back(1);
    nowa[1]++;
    nowb[1]++;
    st[1][1] = true;
    dfs(1, 1);
}

正确代码
#include<bits/stdc++.h>
using namespace std;
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int n,a[20],b[20],max_a[20],max_b[20],m[20][20];
bool vis[20][20],f;
vector<int> ans1,ans2;
bool check(){//判断是否满足题意
	for(int i=1;i<=n;i++){
		if(a[i]!=max_a[i] || b[i]!=max_b[i]) return 0;
	}
	return 1;
}
void dfs(int x,int y){
	if(f) return;//如果已经找到答案则返回
	if(x==n && y==n && check()){
		for(int i=0;i<ans1.size();i++){
			cout<<m[ans1[i]][ans2[i]]<<" ";
		}
		f=1;
		return;
	}
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1 || nx>n || ny<1 || ny>n || a[ny]>=max_a[ny] || b[nx]>=max_b[nx] || vis[nx][ny]) continue;
     //若满足条件则进入下一层递归
		a[ny]++;
		b[nx]++;
		vis[nx][ny]=1;
		ans1.push_back(nx);
		ans2.push_back(ny);
		dfs(nx,ny);
     //回溯
		a[ny]--;
		b[nx]--;
		vis[nx][ny]=0;
		ans1.pop_back();
		ans2.pop_back();
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>max_a[i];
	for(int i=1;i<=n;i++) cin>>max_b[i];
	int t=0;
	for(int i=1;i<=n;i++){//预处理每个格子的编号
		for(int j=1;j<=n;j++){
			m[i][j]=t++;
		}
	}
	vis[1][1]=1;//记得标记起点
	a[1]++;
	b[1]++;
	ans1.push_back(0);
	ans2.push_back(0);
	dfs(1,1);
	return 0;
}

标签:20,int,back,nx,ny,maxn,001DFS
From: https://www.cnblogs.com/hoshino-/p/18355330

相关文章