wave数组找字母游戏

阳光穿透心脏的1/2处 2022-07-21 00:06 161阅读 0赞

# 题目描述： #

Word Maze 是一个网络小游戏，你需要找到以字母标注的食物，但要求以给定单词字母的顺序吃掉。如上图，假设给定单词if，你必须先吃掉i然后才能吃掉f。

但现在你的任务可没有这么简单，你现在处于一个迷宫Maze（n×m的矩阵）当中，里面到处都是以字母标注的食物，但你只能吃掉能连成给定单词W的食物。

，指定W为“SOLO”，则在地图中红色标注了单词“SOLO”。

## 注意区分英文字母大小写,你只能上下左右行走。 ##

运行时间限制: 无限制  
内存限制: 无限制

## 输入: ##

输入第一行包含两个整数n、m(0<n, m<21)分别表示n行m列的矩阵，第二行是长度不超过100的单词W，从第3行到底n+3行是只包含大小写英文字母的长度为m的字符串。

## 输出: ##

如果能在地图中连成给定的单词，则输出“YES”，否则输出“NO”。注意：每个字母只能用一次。

## 样例输入: ##

5 5  
SOLO  
CPUCY  
EKLQH  
CRSOL  
EKLQO  
PGRBC

## 样例输出: ##

YES

# 思路分析： #

*  这道题同样对时间和空间没有要求，所以采用暴力破解
 *  遍历二位数组，寻找对应的单词的字母，找到了要set=‘’，然后conninue

# 代码： #

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Scanner;
     
    public class Main {
    	public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
     	while(scan.hasNext()){
     		int n = scan.nextInt();
     		int m = scan.nextInt();
     		char[][] wave = new char[n][m];
     		String input = scan.next();
     		char[] inputArray = input.toCharArray();
     		for(int i = 0;i < n;i++){
     			String a = scan.next();
     			char[] aArray = a.toCharArray();
     			wave[i] = aArray;
     		}
     		int length = inputArray.length;
     		boolean[] flag = new boolean[length];
     		for(int q = 0;q < length;q++){
    				flag[q] = false;
    			}
     		for(int c = 0;c < length;c++){
     			for(int j = 0;j < n;j++){
     				for(int k = 0;k < m;k++){
     					if(wave[j][k] == inputArray[c]){
     						if(flag[c] == false){
     							flag[c] = true;
     							wave[j][k] = ' ';
     						}
     					}
     				}
     			}
     		}
     		for(int p = 0;p< length;p++){
     			if(flag[p] == false){
     				System.out.println("NO");
     				return;
     			}
     		}
     		System.out.println("YES");
    	}	
     	
        }
    }