小W的数独（搜索）

思路没想到的原因

当时没有什么思路，就去写第5题了（虽然我没写出来）。

思路

对于这道题目，我们可以先从上往下再从左往右来搜索，每次传入这个数的右边，如果不是$*$，再次搜索，如果是$*$，从$1$到$n$遍历每个数字。判断是否合法，如果合法，就赋值，并再次搜索，直到遇到边界，$cnt++$。注意：因为要注意边界范围所以要加上

代码

#include<bits/stdc++.h>
using namespace std;

const int tt=20;
char a[tt][tt];
int cnt=0,n;

bool check(int x,int y,char c){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==x&&j==y){
                continue;
            }
			if(i==x||j==y||i+j==x+y||i-j==x-y){
				if(a[i][j]==c){
                    return 0;
                }
			}
		} 
	} 
	return 1;
}

void dfs(int x,int y){
	if(y==n+1) x++,y=1;
	if(x==n+1){
		cnt++;
	    return ;
	}
	if(a[x][y]!='*'){
        dfs(x,y+1);
    }else{
		for(int i=1;i<=n;i++){
		    if(!check(x,y,i+'0')){
                continue;
            }
		   	a[x][y]=i+'0';
		    dfs(x,y+1);
		    a[x][y]='*';
	    }
	}
}

int main(){
	freopen("sm.in","r",stdin);
	freopen("sm.out","w",stdout);
	cin >>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
            cin >>a[i][j];
        }
	}
	dfs(1,1);
	cout <<cnt;
    return 0;
}

小田的mex变换（找规律）

思路没想到的原因

没有想到一种特判，具体见思路。

思路

其实几种特判：

• 如果满足$a==k||b==k||c==k$，那么输出$0$；
• 如果满足$k>2$，输出$-1$；
• 如果满足$a==0 \&\$$\&\ b==0 \&\$$\&\ c==0\&\$$\&\ k==2||a==1 \&\$$\&\ c==1 \&\$$\&\ k==2||a>1\&\$$\&\ b>1$$\&\ \&\ c>1 \&\$$\&\ k==1$，那么输出$2$；
• 如果满足$a>2 \&\ \&\ b>2 \&\ \&\ c>2 \&\ \&\ k==2$，输出$3$；（没想到）
• 其他输出$1$。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	freopen("mex.in","r",stdin);
	freopen("mex.out","w",stdout);
	int t;
	cin >>t;
	while(t--){
		int a,b,c,k;
		cin >>a>>b>>c>>k;
		if(a==k||b==k||c==k){
			cout <<"0"<<endl;
			continue;
		}else if(k>2){
			cout <<"-1"<<endl;
			continue;
		}else if(a==0&&b==0&&c==0&&k==2||a==1&&b==1&&c==1&&k==2||a>1&&b>1&&c>1&&k==1){
			cout <<"2"<<endl;
			continue;
		}else if(a>2&&b>2&&c>2&&k==2){
			cout <<"3"<<endl;
			continue;
		}else{
			cout <<"1"<<endl;
			continue;
		}
	}
	return 0;
}

小田的绝密计划（bfs广搜）

待更新……

小田的数字游戏（bfs广搜）

思路没想到的原因

当时没有什么思路，就去写第5题了（虽然我没写出来）。

思路

这道题目要在遍历每个点的时候将其他相邻九个点设为$1$，再继续搜索，最后将没有被设为$1$的点加起来即可。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=10,M=10;
int a[N][M],n,m,dis[N][M],cnt;

void f(int x,int y,int z){
	for(int i=-1;i<=1;i++){
    	for(int j=-1;j<=1;j++){
            dis[x+i][y+j]+=z;
        }
    }
}

void dfs(int x,int y,int sum){
    if(y==m+1) x++,y=1;
    if(x==n+1){
        cnt=max(cnt,sum);
        return ;
    }
    if(dis[x][y]==0){
        f(x,y,1);
        dfs(x,y+1,sum+a[x][y]);
        f(x,y,-1);
    }
    dfs(x,y+1,sum);
}

int main(){
    freopen("num.in","r",stdin);
    freopen("num.out","w",stdout);
    int t;
    cin >>t;
    while(t--){
        cin >>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin >>a[i][j];
            }
        }
        cnt=0;
        dfs(1,1,0);
        cout <<cnt<<endl;
    }
    return 0;
}

小W走迷宫（dfs深搜）

待更新……

小田的绝密实验（dfs深搜）

待更新……

谢谢