找单词
标题：找单词 | 时间限制：1秒 | 内存限制：32768K | 语言限制：不限
给一个字符串和一个二维字符数组，如果该字符串存在于该数组中，则按字符串的字符顺序输出字符串每个字符所在单元格的位置下标字符串，如果找不到返回字符串"N"。
1.需要按照字符串的字符组成顺序搜索，且搜索到的位置必须是相邻单元格，其中“相邻单元格”是指那些水平相邻或垂直相邻的单元格。
2.同一个单元格内的字母不允许被重复使用。
3.假定在数组中最多只存在一个可能的匹配。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String num = scanner.nextLine();
char[][] words = new char[Integer.valueOf(num)][Integer.valueOf(num)];
for (int i=0;i<Integer.valueOf(num);i++){
String line = scanner.nextLine();
String[] wordArray = line.split(",");
for (int j=0; j<wordArray.length;j++){
words[i][j] = wordArray[j].charAt(0);
}
}
String word = scanner.nextLine();
Set<String> curs = new LinkedHashSet<>();
boolean isFind = canFind(words,word,Integer.valueOf(num),curs);
if (!isFind){
System.out.println("N");
}else {
StringBuilder sb = new StringBuilder();
for (String cur:curs){
if (!cur.isEmpty()){
String[] indexs =cur.split("\\+");
sb.append(indexs[0]).append(",").append(indexs[1]).append(",");
}
}
sb.setLength(sb.length()-1);
System.out.println(sb.toString());
}
}
public static boolean canFind(char[][] words,String word,int num, Set<String> curs){
char[] wordArray = word.toCharArray();
for (int i=0;i<num;i++){
for (int j=0;j<num;j++){
if (find(words,wordArray,i,j,0,num,curs,"")){
return true;
}
}
}
return false;
}
public static boolean find(char[][] words, char[] wordArray,int i,int j, int k,int num, Set<String> curs,String cur){
if (k==wordArray.length){
return true;
}
if (!(0<=i&&i<num&&0<=j&&j<num)||words[i][j]=='!'){
return false;
}
curs.add(cur);
if (words[i][j]!=wordArray[k]){
curs.remove(cur);
return false;
}
words[i][j] ='!';
cur=i+"+"+j;
curs.add(cur);
boolean isFind=find(words,wordArray,i-1,j,k+1,num,curs,cur)||find(words,wordArray,i+1,j,k+1,num,curs,cur)
||find(words,wordArray,i,j-1,k+1,num,curs,cur)||find(words,wordArray,i,j+1,k+1,num,curs,cur);
words[i][j] =wordArray[k];
return isFind;
}
}
def get_res(grid, word):
m, n, w = len(grid), len(grid[0]), len(word)
def dfs(i, j, k):
if not 0 <= i < m or not 0 <= j < n or grid[i][j] != word[k]:
return False
if k == w - 1:
path.append((i, j))
ans = list()
for a, b in path:
ans.extend([str(a), str(b)])
print(",".join(ans))
return True
grid[i][j] = ""
path.append((i, j))
res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j - 1, k + 1) or dfs(i, j + 1, k + 1)
grid[i][j] = word[k]
path.remove((i, j))
return res
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
while True:
try:
row = int(input())
grid = [input().split(",") for _ in range(row)]
word = input()
path = list()
if not get_res(grid, word):
print("N")
except:
break //190
