专栏文章

题解：P6207 [USACO06OCT] Cows on Skates G

LLuojt95
P6207题解参与者 1已保存评论 0

文章操作

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

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

1.前言

一道典型的迷宫搜索问题~
  • 本身是一道搜索模板题，难就难在它要求输出途经点！
  • 本题是一道 Special Judge ，只需输出任一路径即可AC。
这道题有 DFS 和 BFS 两种做法。

2. DFS 做法

这道题要考虑 visvis 的置 11 。
我们首先要意识到， visvis 无需置 00 。在一般 DFS 中， DFS 函数 returnreturn 后，一切洗牌，重新开始，尘封以前的记忆， visvis 自然归 00 （听上去有 10810^8 点点的玄乎）。而迷宫问题不一样，如果你将它的记忆清除的像金鱼一样，那么它就可能绕圈圈，死循环，最终TLE……
所以， DFS 后不要置 00 ！
AC code：
CPP
#include<bits/stdc++.h> 
using namespace std;
int n,m,num=1;
int ans[10000][2],vis[120][80];
char a[120][80];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void dfs(int x,int y)
{
	if(x==n&&y==m)
    { 
		for(int i=1;i<=num;i++) cout<<ans[i][0]<<' '<<ans[i][1]<<endl;
		return ;
	}
	for(int i=0;i<4;i++)
    {
		int nx=x+dx[i];
        int ny=y+dy[i]; 
		if(nx&&ny&&nx<=n&&ny<=m&&!vis[nx][ny]&&a[nx][ny]=='.')
        {
			vis[nx][ny]=1;
			num++;
			ans[num][0]=nx;
			ans[num][1]=ny;
			dfs(nx,ny);
			num--;
            //不要置 0 !
		}
	}
}
int main()
{	
	cin>>n>>m;
	for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>>a[i][j];
    }
	vis[1][1]=1;
    ans[1][0]=1;
    ans[1][1]=1;
	dfs(1,1);
	return 0;
}

3. BFS做法

如果你选择 BFS 做法，那么你就需要一个 resres 数组，与队列 qq 一样，也需要一个 nodenode 类型的 structstruct 结构体打包两个元素 xx 和 yy 。
为啥呢？res数组就是为了存储一个坐标的父亲节点，形象一些， res[x][y]=res[x][y]= { px,pypx,py } 就代表坐标 (x,y)(x,y) 的上一步是 (px,py)(px,py) 。这样，我们输出时就可以从 endend 一直追溯到 startstart 。
由于 startstart 先输出，我们就可从 (n,m)(n,m) 开始 BFS ，让 (1,1)(1,1) 作为叶子节点， (n,m)(n,m) 作为根节点，这样，程序就可正序输出。
AC code：
CPP
#include<bits/stdc++.h>
#define N 200
using namespace std;
int n,m,hh,tt;
char a[N][N];
int vis[N][N];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
struct node{
	int x,y;
}q[N*N],res[N][N];
void bfs(void)
{
	q[tt++]={n,m};
	vis[n][m]=1;
	while(hh<tt)
	{
		node p=q[hh++];
		for(int i=0;i<4;i++)
		{
			int nx=p.x+dx[i];
			int ny=p.y+dy[i];
			if(nx&&ny&&nx<=n&&ny<=m&&a[nx][ny]!='*'&&!vis[nx][ny])
			{
				q[tt++]={nx,ny};
				vis[nx][ny]=1;
				res[nx][ny]={p.x,p.y};
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) cin>>a[i][j];
	}
	bfs();
	int i=1,j=1;
	while(i!=n||j!=m)
	{
		cout<<i<<' '<<j<<endl;
		node t=res[i][j];
		i=t.x;
		j=t.y;
	}
	cout<<n<<' '<<m;
	return 0;
}

评论

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

正在加载评论...