题目描述
blablabla
样例
blablabla
算法1
(dfs) $O(?)$
include [HTML_REMOVED]
using namespace std;
const int N=22;
int hang[N],lie[N],n,res[N*N],flag[N][N],sum2,sum1=0,sum,k=0,fl=1;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
void dfs(int x,int y,int cnt){
if(x==n&&y==n&&sum==cnt&&sum1==1&&sum2==1&&fl){
//因为路径唯一所以加入哨兵fl保证唯一输出,否则有两个解其中后一个是错的
int l=sum;
// for(int i=1;i<=n;i){
// for(int j=1;j<=n;j)//cout<<flag[i][j]<<” “;cout<<endl;
// if(flag[i][j])
// res[k++]=(i-1)*n+j-1;
// }
cout<<‘0’<<’ ‘;
fl=0;
for(int i=0;i<l-1;i++) cout<<res[i]<<" ";
cout<<endl;
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) continue ;
if(flag[nx][ny]) continue;
if(hang[nx]==0||lie[ny]==0) continue;
flag[nx][ny]=1;
res[k]=(nx-1)*n+ny-1;
hang[nx]--;
lie[ny]--;
sum1--,sum2--;
dfs(nx,ny,cnt+1);
flag[nx][ny]=0;
hang[nx]++;sum1++,sum2++;
lie[ny]++;k--;
}
}
int main()
{
cin>>n;
if(n==0){
cout<<‘0’;
return 0;
}
for(int i=1;i<=n;i) scanf(“%d”,&lie[i]);
for(int i=1;i<=n;i) scanf(“%d”,&hang[i]);
for(int i=1;i<=n;i) sum1+=lie[i];//cout<<lie[i]<<” “;
//cout<<sum1<<endl;
sum2=sum1;
sum=sum1;
flag[1][1]=1;
//res[k]=0;
dfs(1,1,1);
// 请在此输入您的代码
return 0;
}
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla