1 solutions

  • 1
    @ 2025-8-19 23:01:56
    #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