7-22 LC老玩游戏 (30 分)

66 阅读 0 评论 44 点赞

我是靠谱客的博主飞快小鸭子，最近开发中收集的这篇文章主要介绍7-22 LC老玩游戏 (30 分)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

LC 老爱玩游戏了，他的队友为了惩罚他就把他关到了小黑屋学习 dfs 。如果他学会了就可以从小黑屋里出来通过迷宫。迷宫是由 n∗n 个房间组成的矩形，每个房间只和他相邻的房间有一条通道，既如果 LC 在 (X,Y) 房间，那么他一步只能达到 (X+1,Y)(X−1,Y)(X,Y+1)(X,Y−1) 房间。

有一些房间的房门被焊死了，无法进入。也不能走出迷宫的边界，例如在 (1,1) 房间就不能进入 (1,0)(0,1) 这些位置。

LC 一开始被关在小黑屋的位置为迷宫的左上角记为 (1,1) ，迷宫的出口在右下角记为 (n,n) 现在他想知道他有没有机会逃出迷宫，因为有可能他的队伍直接放弃了他，把他永远困在迷宫之中。

输入格式:

第一行给出一个正整数 t(1<=t<=100) 表示样例组数

之后的 t 组数据
第一行给出一个正整数 n(1<=n<=20) 表示迷宫的大小为 n∗n

接下来 n 行，每行给出 n 个整数。

第 i 行的第 j 个数为 0 代表 (i,j) 房间可以进入，为 1 代表不可进入。

保证， (1,1)(n,n) 一定可以进入。

输出格式:

每组数据，在一行内输出输出 "LCyyds" 如果 LC 能够走出迷宫，否则输出 "QwQ"，不带引号。

输入样例:

输出样例:

LCyyds
QwQ

#include<iostream>

using namespace std;

const int N = 30;
int m[N][N];
bool vis[N][N];
int n;

bool inmaze(int x,int y){
    return 1 <= x && x <= n && 1 <= y && y <= n;
}

bool dfs(int x,int y){
   if(x == n && y == n){
        return true;
    }
    m[x][y] = 1;
    int tx = x - 1,ty = y;
    if(inmaze(tx,ty) && m[tx][ty] !=1){
        if(dfs(tx,ty)){
			return true;
        }
    }
    tx = x,ty = y - 1;
    if(inmaze(tx,ty) && m[tx][ty] != 1){
        if(dfs(tx,ty)){
			return true;
        }
    }
    tx = x + 1,ty = y;
    if(inmaze(tx,ty) && m[tx][ty] != 1){
        if(dfs(tx,ty)){
			return true;
        }
    }
    tx = x,ty = y + 1;
    if(inmaze(tx,ty) && m[tx][ty] != 1){
        if(dfs(tx,ty)){
			return true;
        }
    }
    //vis[x][y] = 0;
    return false;
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) cin >> m[i][j];
    bool flag = dfs(1,1);
    if(flag)cout << "LCyyds" << endl;
    else cout << "QwQ" << endl;
}

int main(){
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}