(C卷,200分)- 找单词（Java & JS & Python）

题目描述

给一个字符串和一个二维字符数组，如果该字符串存在于该数组中，则按字符串的字符顺序输出字符串每个字符所在单元格的位置下标字符串，如果找不到返回字符串“N”。

1.需要按照字符串的字符组成顺序搜索，且搜索到的位置必须是相邻单元格，其中“相邻单元格”是指那些水平相邻或垂直相邻的单元格。

2.同一个单元格内的字母不允许被重复使用。

3.假定在数组中最多只存在一个可能的匹配。

输入描述

第1行为一个数字N指示二维数组在后续输入所占的行数。

第2行到第N+1行输入为一个二维大写字符数组，每行字符用半角,分割。

第N+2行为待查找的字符串，由大写字符组成。

二维数组的大小为N*N，0<N<=100。

单词长度K，0<K<1000。

输出描述

输出一个位置下标字符串，拼接格式为：第1个字符行下标+”,”+第1个字符列下标+”,”+第2个字符行下标+”,”+第2个字符列下标… +”,”+第N个字符行下标+”,”+第N个字符列下标。

用例

题目解析

本题和

很像。只是本题在上面这题的基础上，要求保存路径坐标。

题目假定在数组中最多只存在一个可能的匹配。因此我们只要找到即返回。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const path = require("path");
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    n = parseInt(lines[0]);
  }

  if (n && lines.length === n + 2) {
    lines.shift();
    const str = lines.pop();

    const grid = lines.map((line) => line.split(","));

    console.log(findLetter(grid, n, str));

    lines.length = 0;
  }
});

function findLetter(grid, n, str) {
  function dfs(i, j, k, path) {
    if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] !== str[k])
      return false;

    path.push([i, j]);
    if (path.length === str.length) return true;

    const tmp = grid[i][j];
    grid[i][j] = undefined;

    const res =
      dfs(i - 1, j, k + 1, path) ||
      dfs(i + 1, j, k + 1, path) ||
      dfs(i, j - 1, k + 1, path) ||
      dfs(i, j + 1, k + 1, path);

    if (!res) {
      grid[i][j] = tmp;
      path.pop();
    }

    return res;
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const path = [];
      if (dfs(i, j, 0, path)) {
        return path.toString();
      }
    }
  }

  return "N";
}

Java算法源码

import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  static int n;
  static String[][] matrix;
  static String tar;

  public static void main(String[] args) {
    // 将输入分隔符改为“,”和换行
    Scanner sc = new Scanner(System.in).useDelimiter("[,n]");

    n = sc.nextInt();

    matrix = new String[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        matrix[i][j] = sc.next();
      }
    }

    tar = sc.next();

    System.out.println(getResult());
  }

  public static String getResult() {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        LinkedList<Integer[]> path = new LinkedList<>();
        if (dfs(i, j, 0, path)) {
          StringJoiner sj = new StringJoiner(",");
          for (Integer[] pos : path) sj.add(pos[0] + "," + pos[1]);
          return sj.toString();
        }
      }
    }
    return "N";
  }

  public static boolean dfs(int i, int j, int k, LinkedList<Integer[]> path) {
    if (i < 0 || i >= n || j < 0 || j >= n || !tar.substring(k, k + 1).equals(matrix[i][j])) {
      return false;
    }

    path.add(new Integer[] {i, j});
    if (path.size() == tar.length()) return true;

    String tmp = matrix[i][j];
    matrix[i][j] = null;

    boolean res =
        dfs(i - 1, j, k + 1, path)
            || dfs(i + 1, j, k + 1, path)
            || dfs(i, j - 1, k + 1, path)
            || dfs(i, j + 1, k + 1, path);

    if (!res) {
      matrix[i][j] = tmp;
      path.removeLast();
    }

    return res;
  }
}

Python算法源码

# 输入获取
n = int(input())
matrix = [input().split(",") for _ in range(n)]
tar = input()


def dfs(i, j, k, path):
    if i < 0 or i >= n or j < 0 or j >= n or matrix[i][j] != tar[k]:
        return False

    path.append([i, j])
    if len(path) == len(tar):
        return True

    tmp = matrix[i][j]
    matrix[i][j] = ""

    res = dfs(i - 1, j, k + 1, path) or dfs(i + 1, j, k + 1, path) or dfs(i, j - 1, k + 1, path) or dfs(i, j + 1, k + 1, path)

    if not res:
        matrix[i][j] = tmp
        path.pop()

    return res


# 算法入口
def getReuslt():
    for i in range(n):
        for j in range(n):
            path = []
            if dfs(i, j, 0, path):
                return ",".join(map(lambda x: ",".join(map(str, x)), path))

    return "N"


# 算法调用
print(getReuslt())