麻烦各位帮忙看看,我这个问题出在哪里了,十分感谢
查看原帖
麻烦各位帮忙看看,我这个问题出在哪里了,十分感谢
1111062
jyl_by楼主2024/2/25 19:52
#include<bits/stdc++.h>
#include <iostream>
using namespace std;

int hang_ba[23],lie_ba[23];
int Map[23][23],visit[23][23];
int dx[]= {1,-1,0,0};
int dy[]= {0,0,1,-1};
vector<int> trace;

bool check_end(int x,int y,int n)
{
    for(int i=0; i<n; i++)
    {
        if(hang_ba[i]) return false;
    }
    for(int i=0; i<n; i++)
    {
        if(lie_ba[i]) return false;
    }
    if(!(x==n-1&&y==n-1)) return false;
    return true;

}
bool check_worth(int x,int y,int n)
{
    if(visit[x][y]) return false;
    if(hang_ba[x]<=0||lie_ba[y]<=0) return false;
    if(x < 0 || x >= n || y < 0 || y >= n) return false;
    return true;
}

void dfs(int x,int y,int n)
{
    for(int i=0; i<n; i++)
    {
        int fx=x+dx[i],fy=y+dy[i];
        if(check_worth(fx,fy,n))
        {
            trace.push_back(Map[fx][fy]);
            hang_ba[fx]--;
            lie_ba[fy]--;
            visit[fx][fy]=1;
            if(check_end(fx,fy,n))
            {
                for(int i=0; i<trace.size(); i++)
                {
                    cout << trace[i] << " ";
                }
                return ;
            }
            else
            {
                dfs(fx,fy,n);
            }
            dfs(fx,fy,n);
            visit[fx][fy]=0;
            trace.pop_back();
            hang_ba[fx]++;
            lie_ba[fy]++;
        }
    }
}

int main()
{
    int n,temp;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            Map[i][j]=temp++;
        }
    }
    for(int i = 0 ; i < n ; i++) cin >> lie_ba[i];
    for(int i = 0 ; i < n ; i++) cin >> hang_ba[i];
    visit[0][0]=1;
    hang_ba[0]--;
    lie_ba[0]--;
    trace.push_back(0);
    dfs(0,0,n);
    return 0;
}
2024/2/25 19:52
加载中...