问一道网站外的题目——迷宫
  • 板块学术版
  • 楼主Wei_wei_
  • 当前回复33
  • 已保存回复33
  • 发布时间2020/7/23 17:21
  • 上次更新2023/11/6 22:29:58
查看原帖
问一道网站外的题目——迷宫
313727
Wei_wei_楼主2020/7/23 17:21

谢谢@Crazy_Bucket上次的帮助,可惜我还不知道我错在了哪儿。怕在后面的贴不太好找,所以再次提问:题目:

1215:迷宫

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 20184     通过数: 5940 
【题目描述】
一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。

【输入】
第1行是测试数据的组数k,后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 ≤ n ≤ 100),表示迷宫的规模是n * n的。接下来是一个n * n的矩阵,矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb,描述A处在第ha行, 第la列,B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。

【输出】
k行,每行输出对应一个输入。能办到则输出“YES”,否则输出“NO”。

【输入样例】
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
【输出样例】
YES
NO

我的代码:

#include<iostream>
using namespace std;
int n;
int x,y,x1,y1;
char a[100][100];
bool f(int i)
{
	if(a[x1][y1]=='*')return true;
	if(a[x1][y1]=='#')return false;
	if(a[x][y]=='#')return false;
	if(i>=n*n)return false;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(a[i][j]=='*')
			{
				if(a[i+1][j]!='#')
				a[i+1][j]='*';
				if(a[i-1][j]!='#')
				a[i-1][j]='*';
				if(a[i][j+1]!='#')
				a[i][j+1]='*';
				if(a[i][j-1]!='#')
				a[i][j-1]='*';
			}
	f(i+1);
}
int main()
{
	int k;
	cin>>k;
	while(k--)
	{
		cin>>n;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				cin>>a[i][j];
		cin>>x>>y>>x1>>y1;
		if(a[x][y]!='#')
		a[x][y]='*';
		/*f(1);
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
				cout<<a[i][j];
			cout<<'\n';
		}*/
		if(f(1)==true)cout<<"YES\n";
		else cout<<"NO\n";
	}
}
2020/7/23 17:21
加载中...