专栏文章

8.23测试总结

LLuck_Deepsea
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio6ck6d
此快照首次捕获于
2025/12/02 14:05
3 个月前
此快照最后确认于
2025/12/02 14:05
3 个月前
查看原文

8.218.21测试总结

T658911五子棋T658911 五子棋

得分:2020

应得:100100

考点:深搜-深度优先搜索（dfsdfs）

错误思路:暴力-打表，写出n>=...n>=...就将计数器加......

正确思路:搜索枚举出所有情况，如果没出现就将计数器加kk，输出。(kk是check函数中的表示有多少个5个子起来的直线)

check函数：

CPP
int check(){
	int k=0;
	for(int i=1;i<=5;i++){
		int cnt=0;
		for(int j=1;j<=5;j++)cnt+=vis[i][j];
		if(cnt==5)k++;
	}
	for(int i=1;i<=5;i++){
		int cnt=0;
		for(int j=1;j<=5;j++)cnt+=vis[j][i];
		if(cnt==5)
			k++;
	}
	int cnt=0;
	for(int i=1;i<=5;i++)cnt+=vis[i][i];
	if(cnt==5)k++;
	cnt=0;
	for(int i=1;i<=5;i++)cnt+=vis[i][6-i];
	if(cnt==5)k++;
	return k;
}

搜索过程：

CPP
void dfs(int x,int y,int cnt){
	if(cnt==n){
		int k=check();
		tong[k]++;
		if(tong[k]==1)ans+=k;
		return ;
	}
	if(x==6)return ;
	if(y==5){
		vis[x][y]=1;
		dfs(x+1,1,cnt+1);
		vis[x][y]=0;
		dfs(x+1,1,cnt);
	}
	else{
		vis[x][y]=1;
		dfs(x,y+1,cnt+1);
		vis[x][y]=0;
		dfs(x,y+1,cnt);
	}
	return ;
}

完整代码:

CPP
#include<bits/stdc++.h>
using namespace std;
int n;
int tong[25];
int ans=0;
int vis[25][25];
int check(){
	int k=0;
	for(int i=1;i<=5;i++){
		int cnt=0;
		for(int j=1;j<=5;j++)cnt+=vis[i][j];
		if(cnt==5)k++;
	}
	for(int i=1;i<=5;i++){
		int cnt=0;
		for(int j=1;j<=5;j++)cnt+=vis[j][i];
		if(cnt==5)
			k++;
	}
	int cnt=0;
	for(int i=1;i<=5;i++)cnt+=vis[i][i];
	if(cnt==5)k++;
	cnt=0;
	for(int i=1;i<=5;i++)cnt+=vis[i][6-i];
	if(cnt==5)k++;
	return k;
}
void dfs(int x,int y,int cnt){
	if(cnt==n){
		int k=check();
		tong[k]++;
		if(tong[k]==1)ans+=k;
		return ;
	}
	if(x==6)return ;
	if(y==5){
		vis[x][y]=1;
		dfs(x+1,1,cnt+1);
		vis[x][y]=0;
		dfs(x+1,1,cnt);
	}
	else{
		vis[x][y]=1;
		dfs(x,y+1,cnt+1);
		vis[x][y]=0;
		dfs(x,y+1,cnt);
	}
	return ;
}
int main()
{
	cin>>n;
	dfs(1,1,0);
	cout<<ans<<endl;
	return 0;   
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...