2024-01-18竞赛笔记

2024/1/18

//P1596 [USACO10OCT] Lake Counting S
#include<bits/stdc++.h>
using namespace std;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};//各个方向
int a[1001][1001];//保存地图
int n,m,ans;
void dfs(int x,int y)
{
	for(int i=0;i<=7;i++)//向8个方向枚举
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(a[xx][yy]==1)//只要找到联通得水坑就标记为0 
		{
			a[xx][yy]=0;
			dfs(xx,yy);
		}	
	} 
	return;
} 

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='.') a[i][j]=0;//1为水坑，0为旱地 
			else a[i][j]=1; //判断出界
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){//枚举每一个点
			if(a[i][j]==1){
				ans++;
				dfs(i,j);
			} 
		}
	} 
	cout<<ans<<endl;
	return 0;
}

//P1025 [NOIP2001 提高组] 数的划分 
//DFS做法
#include<bits/stdc++.h>
using namespace std;
int n,k,sum;
void dfs(int s,int t,int l)//last表示前一个状态 
{
	if(s>k)
	{
		if(t==n) sum++;
		return;
	}
	for(int i=l;i<=n-t;i++)//剪枝优化，因为当前格子可选数最大只有n-t 
	{
		dfs(s+1,t+i,i);
	}
}
signed main()
{
	cin>>n>>k;
	dfs(1,0,1);
	cout<<sum;
	
}

//P2036 [COCI 2008/2009 #2] PERKET
#include<bits/stdc++.h>
using namespace std;
int n,a[1001],b[1001],ans=0x3f3f3f3f;//ans初始化，此处约等于INT_MAX
void dfs(int i,int x,int y) //i是第几种配料，x,y代表酸,苦度
{
	if(i>n){
		if(x==1 && y==0) return;
		ans=min(abs(x-y),ans);//取绝对值与当前答案进行比较 
		return;
	} 
	dfs(i+1,x*a[i],y+b[i]);//添加第i种配料 ,总的酸度为每一种配料的酸度总乘积
	dfs(i+1,x,y); //不添加第i中配料
} 

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	dfs(1,1,0);//配料编号，酸度(乘法默认初值为1)，苦度（默认初值为0）
	cout<<ans<<endl;
	return 0; 
}

//P1784 数独
#include<bits/stdc++.h>
using namespace std;
int g[9][9];
int cell[3][3][10],row[9][10],col[9][10];//保存数独信息
bool dfs(int x,int y)
{
	if(y==9) x++,y=0;
	if(x==9) return true;
	if(g[x][y]) return dfs(x,y+1);
	else
	{
		for(int i=1;i<=9;i++)//开始判断行、列、宫
		{
			if(cell[x/3][y/3][i] || row[x][i] || col[y][i]) continue;
			g[x][y]=i;//保存
			cell[x/3][y/3][i]=row[x][i]=col[y][i]=true;
			if(dfs(x,y+1)) return true;
			g[x][y]=0;//回溯
			cell[x/3][y/3][i]=row[x][i]=col[y][i]=false;
		} 
	}
	return false;
	/*
	while(false)
	{
		cout<<"renjiheinu"<<endl;
	}
	*/
} 

signed main()
{
	for(int i=0;i<9;i++)//输入数独 
	{
		for(int j=0;j<9;j++)
		{
			cin>>g[i][j];
			if(g[i][j])//如果已经有数
			{
				int x=g[i][j];	
				cell[i/3][j/3][x]=row[i][x]=col[j][x]=true;
			} 
		}
	}
	//初始化 
	dfs(0,0);
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++) cout<<g[i][j]<<' ';
		cout<<endl;
	}
	return 0;
}

P1238 走迷宫

P1605 迷宫

【初一算法基础】深搜与回溯

BFS（图论）-OI Wiki