小W的数独

思路

把所有可以的结果遍历一遍（dfs）。

代码

#include<bits/stdc++.h>
using namespace std;
char a[15][15];
int idx=0,cnt;
pair<int,int> s[100];
int n;
bool cheek(int x,int y,int is){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==x){
				if(a[i][j]==is+'0'){
					return false;
				}
			}
			if(j==y){
				if(a[i][j]==is+'0'){
					return false;
				}
			}
			if(x-y+n==i-j+n){
				if(a[i][j]==is+'0'){
					return false;
				}
			}
			if(x+y+n==i+j+n){
				if(a[i][j]==is+'0'){
					return false;
				}
			}
		}
	}
	return true;
}
void dfs(int l){
	if(l==idx){
		cnt++;
		return ;
	}
	int x=s[l].first,y=s[l].second;
	for(int i=1;i<=n;i++){
		if(cheek(x,y,i)){
			a[x][y]=i+'0';
			dfs(l+1);
			a[x][y]='*';
		}
	}
}
int main(){
	freopen("sm.in","r",stdin);
	freopen("sm.out","w",stdout);
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>a[i][j];
			if(a[i][j]=='*'){
				s[idx].first=i;
				s[idx++].second=j;
			}
		}
	}
	dfs(0);
	cout<<cnt;
	return 0;
}

反思

没有考虑暴力怎么写，所以错失了机会。 以后应当考虑暴力的时间空间，如果可以就用暴力

小田的mex变换

思路

本题我用了分类讨论

1. 如果有一个数等于$k$，那么就输出0。
2. 如果$k$>2，就怎么也求不到了。因为$mex(0,1)$只能求到2，$mex(1,2)$也求不到，不可能填3个数。
3. 如果k==2且abc中有$0$和$1$，那么就只要$mex(0,1)$
4. 如果k==2（上面的不成立）。那么只能造0和1，所以3步
5. 如果k==1且abc中有0，那么只要一步$mex(0,y)$
6. 如果k==1（上面的不成立），那么就要先造0，故2步
7. 如果k==0，那么直接就可以得出来（1步）

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("mex.in","r",stdin);
	freopen("mex.out","w",stdout);
	int n;
	cin>>n;
	while(n--){
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	if(k==b||k==a||k==c){
		cout<<0<<endl;
		continue;
	}
	if(k>=3){
		cout<<-1<<endl;
		continue;
	}
	if(k==2&&(a==1||b==1||c==1)&&(a==0||b==0||c==0)){
		cout<<1<<endl;
		continue;
	}
	if(k==2){
		//伍衍
		cout<<3<<endl;
		continue;
	}
	if(k==1&&(a==0||b==0||c==0)){
		cout<<1<<endl;
		continue;
	}
	if(k==1){
		cout<<2<<endl;
		continue;
	}
	if(k==0){
		cout<<1<<endl;
		continue;
	}
	}
	return 0;
}

反思

理解错了题目意思，以为是在$x—y$中选一个 最小值，以后定当将题目关键信息批注好，不要再出现这样的惨状。

小田的绝密计划

思路

广搜的灵活变换。

代码

#include<bits/stdc++.h>
using namespace std;
struct P{
	int x,y,steep;
};
int dx[]={0,1,0,-1},dy[]={1,0,-1,0},as[100010][2],bs[100010][2],st[510][510];
int n,m,a,b;
queue<P> q;
void ter(){
	while(q.size()){
		P now=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			P now2;
			now2.x=now.x+dx[i];
			now2.y=now.y+dy[i];
			now2.steep=now.steep+1;
			if(now2.x>n||now2.y>m||now2.x<1||now2.y<1){
				continue;
			}
			if(st[now2.x][now2.y]<=now2.steep){
				continue;
			}
			q.push(now2);
			st[now2.x][now2.y]=now2.steep;
			//cout<<now.x<<" "<<now.y<<" "<<now.steep<<" "<<st[now.x][now.y]<<endl;
		}
	}
}
int main(){
	freopen("bd.in","r",stdin);
	freopen("bd.out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(st,0x3f3f3f3f,sizeof st);
	cin>>n>>m>>a>>b;
	for(int i=1;i<=a;i++){
		int x,y;
		cin>>x>>y;
		q.push(P{x,y,0});
		st[x][y]=0;
	}
	for(int i=1;i<=b;i++){
		cin>>bs[i][0]>>bs[i][1];
	}
	ter();
	for(int i=1;i<=b;i++){
		cout<<st[bs[i][0]][bs[i][1]]<<endl;
	}
	
	return 0;
}

反思

这题我知道了广搜可以将多个起点塞入队列，也不会影响结果