游客 注册 | 登录
中文 | En

1982 - 迷宫判断

通过次数

0

提交次数

0

时间限制 : 3 秒 内存限制 : 128 MB

小明最近沉迷与一个游戏，但是他在玩游戏中经常遇到各种各样的迷宫，其中既有走得通的迷宫也有走不通的迷宫。

小明懒得费这个力，想让你帮忙写一个程序帮他一劳永逸地解出所有的迷宫。

题目输入

第一行输入一个正整数n，代表待求解的迷宫的数量。

其后n组数据，每组数据输入一个数m，代表迷宫的长度和宽度。

其后输入m行，m列的一个矩阵，其中0代表此格有障碍，不能通行，1代表可以通过。

数据保证最左上角和最右下角的格子不会有障碍。

迷宫不会大于30x30。

题目输出

判断每个迷宫是否能从左上角的起点走到右下角的终点，每个迷宫输出“YES”或“NO”代表这个迷宫是否可以走通。

输入/输出样例

输入格式

2
3
1 1 0
0 1 1
0 0 1
4
1 1 0 1
0 0 1 1
1 1 0 1
1 1 0 1

输出格式

YES
NO

C++解答

#include<iostream>
#include<cstring>
using namespace std;
int n;
bool b[31][31]={0};

const int dx[4]={0,0,1,-1},
          dy[4]={-1,1,0,0};		

void bfs()
{
	int h=1,t=1,x,y;
	int q[10001][3]={0};	
		q[1][0]=1;
		q[1][1]=1;
		q[1][2]=0;
		
		b[1][1]=0;
	while(h<=t)
	{
	
		
		
		for(int i=0;i<4;++i)
		{
			 x=q[h][0]+dx[i];
			 y=q[h][1]+dy[i];
			if(x>0&&y>0&&x<=n&&y<=n&&b[x][y]==1)
			{
				t++;
				q[t][0]=x;
				q[t][1]=y;
				b[x][y]=0;
				q[t][2]=q[h][2]+1;
			if(x==n&&y==n)
			{
			cout<<"YES"<<endl;
			return;
			}
			}
		}
		
		h++;
	}
	cout<<"NO"<<endl;
	return;
	
}
int main()
{
    int k;
    cin>>k;
    for(int u=1;u<=k;++u)
    {
      cin>>n;
      for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
          cin>>b[i][j];
      bfs();
    }
    return 0;
}

Python解答

# coding=utf-8
n=int(input())
m=[]
s=[]
p=1
for i in range(n):
    a=int(input())
    m.append(a)
    for j in range(a):
        b=list(map(int,input().split()))
        s.append(b)
for l in range(n):
    for k in range(m[l]-1):
        for i in range(k-1):
            if s[k][i]!=0 and (s[k+1][i]!=0 or s[k][i+1]!=0):
                p=1
            else:
                p=0
    if l==0:
        if s[m[l]-1][m[l]-1]==p:
            print("YES")
        else:
            print("NO")
    else:
        if s[m[l-1]+m[l]-1][m[l]-1]==p:
            print("YES")
        else:
            print("NO")
请先登陆