- C++
搜索与回溯作业
- 2024-8-17 12:01:12 @
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[4][15],b[15],c[15],ans,flag;
bool jiancha(){
int a1=0,a2=0,a3=0;
for(int i=1;i<=10;i++){
if(c[i]==a[1][i])a1++;
if(c[i]==a[2][i])a2++;
if(c[i]==a[3][i])a3++;
}
a1*=10,a2*=10,a3*=10;
if(a1==70&&a2==50&&a3==30){
return true;
}else return false;
}
int pp(){
for(int i=1;i<=10;i++){
if(c[i]==b[i]){
ans++;
}
}
ans*=10;
cout<<ans;
return 0;
}
int dfs(int t){
if(t>10||flag==1){
if(jiancha()){
pp();
flag = 1;
}
return 0;
}
for(int i=0;i<=1;i++){
c[t]=i;
dfs(t+1);
}
return 0;
}
int main(){
for(int i=1;i<=3;i++){
for(int j=1;j<=10;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=10;i++){
cin>>b[i];
}
dfs(1);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,t,sx,sy,fx,fy,a[10][10],ans=0;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int dfs(int x,int y){
if(x==fx&&y==fy){
ans++;
return 0;
}
a[x][y] = 1;
for(int i=0;i<4;i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(a[nx][ny]==0&&nx>=1&&ny>=1&&nx<=n&&ny<=m){
a[nx][ny]=1;
dfs(nx,ny);
a[nx][ny]=0;
}
}
return 0;
}
int main(){
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
for(int i=1;i<=t;i++){
int tx,ty;
cin>>tx>>ty;
a[tx][ty]=1;
}
dfs(sx,sy);
cout<<ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,a[110][110],max_ans,c[110],d[110];
bool chick_i(int x){
int flag=0;
for(int i=1;i<=n;i++){
if(c[i]==1){
if(a[x][i]==1){
flag =1;
}
}
}
if(flag==0)return true;
else return false;
}
int dfs(int t){
if(t-1>max_ans){
max_ans=t-1;
for(int i=1;i<=n;i++){
d[i]=c[i];
}
}
for(int i=1;i<=n;i++){
if(c[i]==0){
if(chick_i(i)){
c[i]=1;
dfs(t+1);
c[i]=0;
}
}
}
return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a1,a2;
cin>>a1>>a2;
a[a1][a2]=1;
a[a2][a1]=1;
}
dfs(1);
cout<<max_ans<<endl;
for(int i=1;i<=n;i++){
cout<<d[i]<<" ";
}
return 0;
}
0 条评论
目前还没有评论...