1 solutions
-
0
Guest MOD
-
1
#include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int fx[]={0,1,-1,2,-2,0,1,-1,1}; const int fy[]={0,1,1,1,1,1,0,2,2}; // 8 种移动方法的偏移量数组 int a[20],b[20],vis[20],cnt[20],tail; bool flag; int f(int x,int y){ // 给定一组下标,为其重新编号的值 if(x==1&&y==1) return 1; if(x==1&&y==2) return 2; if(x==1&&y==3) return 3; if(x==2&&y==1) return 4; if(x==2&&y==2) return 5; if(x==2&&y==3) return 6; if(x==3&&y==1) return 7; if(x==3&&y==2) return 8; if(x==3&&y==3) return 9; } int fffx(int num){ // 对于每一个新的编号,返回其的 x 坐标 if(num==1) return 1; if(num==2) return 1; if(num==3) return 1; if(num==4) return 2; if(num==5) return 2; if(num==6) return 2; if(num==7) return 3; if(num==8) return 3; if(num==9) return 3; } int fffy(int num){// 同理,对于每一个新的编号,返回其的 y 坐标 if(num==1) return 1; if(num==2) return 2; if(num==3) return 3; if(num==4) return 1; if(num==5) return 2; if(num==6) return 3; if(num==7) return 1; if(num==8) return 2; if(num==9) return 3; } bool check(){ memset(cnt,0,sizeof cnt); for(int id=2;id<=9;id++){ int x=fffx(b[id]),y=fffy(b[id]); // 当前下标 int xx=fffx(b[id-1]),yy=fffy(b[id-1]); // 上一个点的下标 if(y<yy){ swap(x,xx); swap(y,yy); } else if(x<xx&&y==yy){ swap(x,xx); swap(y,yy); } // 使 (x,y) 与 (xx,yy) 有序 bool op=false; for(int i=1;i<=8;i++){ if((x-xx)==fx[i]&&(y-yy)==fy[i]){ cnt[i]++; op=true; } } if(op==false) return false; // 判定是否存在一种移动方式,使得能从 (x,y) 移动到 (xx,yy) } for(int i=1;i<=8;i++){ // 检查每种操作的个数是否满足题目所给定条件(即输入) if(a[i]==1994) continue; if(a[i]==-1&&cnt[i]) return false; if(a[i]>=0&&a[i]<cnt[i]) return false; } return true; } void dfs(int x,int y,int tot){ if(tot==9){ if(check()) flag=true; return; } for(int i=1;i<=9;i++){ if(vis[i]) continue; // 已经用过了 vis[i]=1; b[++tail]=i; dfs(fffx(i),fffy(i),tot+1); // 往下递归 vis[i]=0; // 对称 tail--; } } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int T; cin>>T; while(T--){ int sx,sy; cin>>sx>>sy; for(int i=1;i<=8;i++) cin>>a[i]; flag=false; // 重置 vis[f(sx,sy)]=1; b[++tail]=f(sx,sy); dfs(sx,sy,1); // dfs 向后寻找 vis[f(sx,sy)]=0; tail--; // 对称 if(flag==true) cout<<"Y"<<endl; else cout<<"N"<<endl; //输出 } return 0; }希望对大家有帮助,制作不易,点个赞吧
Information
- ID
- 1566
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- (None)
- # Submissions
- 53
- Accepted
- 7
- Uploaded By