复健\(Day6\)

注：这一篇笔记里的搜索题都非常简单

搜索二

\(1.\)迷宫

https://www.luogu.com.cn/problem/P1605

不要忘了回溯

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 10
using namespace std;

int mg[maxn][maxn];
int ans;
int dirx[4]={1,-1,0,0};
int diry[4]={0,0,1,-1};
int sx,sy,tx,ty;
int n,m,t;

void dfs(int x,int y)
{
	if(x==tx&&y==ty)
	{
		ans++;
		return;
	}
	for(int i=0;i<4;i++)
	{
		int nx=x+dirx[i];
		int ny=y+diry[i];
		if(mg[nx][ny]==1&&nx>=1&&nx<=n&&ny>=1&&ny<=m)
		{
			mg[nx][ny]=-1;
			dfs(nx,ny);
			mg[nx][ny]=1;
		}
	}
}

int main()
{
	cin>>n>>m>>t;
	cin>>sx>>sy>>tx>>ty;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) mg[i][j]=1;
	}
	for(int i=1;i<=t;i++)
	{
		int x,y;
		cin>>x>>y;
		mg[x][y]=-1;
	}
	mg[sx][sy]=-1;
	dfs(sx,sy);
	printf("%d\n",ans);
	return 0;
}

这道题有个非常重要的点：我们要把起点设为不能访问，如果不这样的话，我们可能会走过起点两次，这样你的答案就会多于正确答案

\(2.\)跳马

https://www.luogu.com.cn/problem/P1644

因为一直是往右的，所以我们不需要写回溯（因为不会跳到原来走过的点）

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 20
using namespace std;

int ans;
int dirx[4]={1,2,2,1};
int diry[4]={2,1,-1,-2};
int n,m;

void dfs(int x,int y)
{
	if(x==m&&y==n)
	{
		ans++;
		return;
	}
	for(int i=0;i<4;i++)
	{
		int nx=x+dirx[i];
		int ny=y+diry[i];
		if(nx>=0&&nx<=m&&ny>=0&&ny<=n)
		{
			dfs(nx,ny);
		}
	}
}

int main()
{
	cin>>n>>m;
	dfs(0,0);
	printf("%d\n",ans);
	return 0;
}

\(3.\)八皇后问题

https://www.luogu.com.cn/problem/P1219

注意因为我们用到了\(y-x+13\)，所以我们的数组要开大一点

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 30
using namespace std;

int ansnum;
int ans[5][maxn];
int row[maxn];
int col[maxn],L[maxn],R[maxn];//左对角线y-x+13，右对角线y+x 
int n;

void dfs(int x)
{
	if(x==n+1)
	{
		ansnum++;
		if(ansnum<=3)
		{
			for(int i=1;i<=n;i++) ans[ansnum][i]=row[i];
		}
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!col[i]&&!L[i-x+13]&&!R[i+x])
		{
			col[i]=1;
			L[i-x+13]=1;
			R[i+x]=1;
			row[x]=i;
			dfs(x+1);
			col[i]=0;
			L[i-x+13]=0;
			R[i+x]=0;
		}
	}
}

int main()
{
	cin>>n;
	dfs(1);
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=n;j++) printf("%d ",ans[i][j]);
		printf("\n");
	}
	printf("%d\n",ansnum);
	return 0;
}

\(4.\)水坑计数（连通性问题）

https://www.luogu.com.cn/problem/P1596

第一种方法：\(DFS\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 110
using namespace std;

char mg[maxn][maxn];
int n,m;
int dx[8]={-1,-1,-1,0,1,1,1,0};
int dy[8]={-1,0,1,1,1,0,-1,-1};

void dfs(int x,int y)
{
	mg[x][y]='.';
	for(int i=0;i<8;i++)
	{
		int tx=x+dx[i],ty=y+dy[i];
		if(mg[tx][ty]=='W') dfs(tx,ty);
	}
}

int main()
{
	cin>>n>>m;
	int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++) cin>>mg[i][j];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(mg[i][j]=='W')
			{
				ans++;
				dfs(i,j);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

第二种方法：\(BFS\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define maxn 110
using namespace std;

char mg[maxn][maxn];
int n,m;
int dx[8]={-1,-1,-1,0,1,1,1,0};
int dy[8]={-1,0,1,1,1,0,-1,-1};

void bfs(int x,int y)
{
	queue<pair<int,int> > q;
	q.push({x,y});
	mg[x][y]='.';
	while(!q.empty())
	{
		pair<int,int> x=q.front();
		q.pop();
		for(int i=0;i<8;i++)
		{
			int a=x.first+dx[i],b=x.second+dy[i];
			if(mg[a][b]=='W')
			{
				mg[a][b]='.';
				q.push({a,b});
			}
		}
	}
}

int main()
{
	cin>>n>>m;
	int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++) cin>>mg[i][j];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(mg[i][j]=='W')
			{
				ans++;
				bfs(i,j);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

\(5.\)矩阵距离

给定一个\(N\)行\(M\)列的\(01\)矩阵\(A\)，\(A[i][j]\)和\(A[k][l]\)之间的曼哈顿距离为\(dis=|k-i|+|l-j|\)

输出为一个\(N\)行\(M\)列的证书矩阵你\(B\)，其满足\(B[i][j]=min_{1\leqslant x\leqslant N,1\leqslant y\leqslant M,A[x][y]=1}dis(A[i][j],A[x][y])\)

思路：洪水从多个源点\(g[x][y]==1\)，每秒扩展一步，先到哪个点，哪个点就确定最小距离

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 15
using namespace std;

char g[maxn][maxn];
int dis[maxn][maxn];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int n,m;

struct Node
{
	int x,y;
};

void bfs()
{
	memset(dis,-1,sizeof(dis));
	queue<Node> q;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(g[i][j]=='1')
			{
				dis[i][j]=0;
				q.push({i,j});
			}
		}
	}
	while(!q.empty())
	{
		Node u=q.front();
		q.pop();
		int x=u.x,y=u.y;
		for(int i=0;i<4;i++)
		{
			int tx=x+dx[i],ty=y+dy[i];
			if(tx<0||tx>=n||ty<0||ty>=m) continue;
			if(dis[tx][ty]!=-1) continue;
			dis[tx][ty]=dis[x][y]+1;
			q.push({tx,ty});
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++) cin>>g[i][j];
	}
	bfs();
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++) printf("%d ",dis[i][j]);
		printf("\n");
	}
	return 0;
}

\(6.\)八数码难题

https://www.luogu.com.cn/problem/P1379

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<unordered_map>
#define maxn 10
using namespace std;

unordered_map<string,int> d;
queue<string> q;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int bfs(string str)
{
	q.push(str);
	string end="123804765";;
	while(q.size())
	{
		string s=q.front();
		q.pop();
		if(s==end) return d[s];
		int k=s.find('0');
		int x=k/3,y=k%3;//下标位置的转换
		for(int i=0;i<4;i++)
		{
			int tx=x+dx[i],ty=y+dy[i];
			if(tx<0||tx>=3||ty<0||ty>=3) continue;
			int dis=d[s];
			swap(s[k],s[tx*3+ty]);
			if(!d.count(s)) d[s]=dis+1,q.push(s);
			swap(s[k],s[tx*3+ty]);
		}
	}
}

int main()
{
	string s;
	cin>>s;
	printf("%d\n",bfs(s));
	return 0;
}