思路:深度优先搜索

问题转化：给你一个M*M的矩阵。然后你要在里面上下左右走出一条路径，这个路径要对应所给的序列。输出下标序列。并且这个下标序列在所有方案中要是最小的。

如果不考虑字典序最小:一个很显然的方式就是枚举所有坐标(x , y)，然后从(x , y)开始往四周dfs搜索，递归条件是路径的每一步需要和序列的数字进行匹配。搜索到一条，则直接输出就行。

现在的问题是，可行方案或许很多，比如：

明文是 0 3

密文矩阵是:

0 3

0 3

那么可行解有两个:"0 0 0 1" 和 "1 0 1 1"。这个题目里需要输出的是0 0 0 1 而不是1 0 1 1。

首先，为了让起始坐标作为字典序最小，我们枚举坐标的顺序应该是一行一行找，如果在一个位置上dfs找到了，就直接退出。这样可以保证开头的字典序是最小的

其次，为了保证整体字典序最小，我们在dfs的过程中，要保持一个"上 左 右 下"的顺序进行搜索。这样搜出来的第一种可行方案就是字典序最小的。

C++

#include <iostream>
#include <vector>

using namespace std;

int a[100];
int mp[100][100];
int n, m;
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};

bool dfs(int x, int y, int pos, vector<int>& ans) {
    ans.push_back(x);
    ans.push_back(y);
    int gg = mp[x][y];
    mp[x][y] = -1;
    if (pos == n - 1) {
        return true;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (!(nx < 0 || nx >= m || ny < 0 || ny >= m || mp[nx][ny] != a[pos + 1])) {
            if (dfs(nx, ny, pos + 1, ans)) {
                return true;
            }
        }
    }
    mp[x][y] = gg;
    for (int i = 0; i < 2; i++) {
        ans.pop_back();
    }
    return false;
}

void readIn() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
        }
    }
}

void outPutList(const vector<int>& arr) {
    for (int k = 0; k < arr.size(); k++) {
        cout << arr[k] << " ";
    }
    cout << endl;
}

int main() {
    readIn();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            vector<int> ans;
            if (mp[i][j] == a[0] && dfs(i, j, 0, ans)) {
                outPutList(ans);
                return 0;
            }
        }
    }
    cout << "error" << endl;
    return 0;
}

Java

import java.util.*;

public class Main {

    static int[] a;
    static int[][] mp;
    static int n, m;
    static int[] dx = {-1, 0, 0, 1}; 
    static int[] dy = {0, -1, 1, 0};
    
    static boolean dfs(int x, int y, int pos, List<Integer> ans) {
        ans.add(x);
        ans.add(y);
        int gg = mp[x][y];
        mp[x][y] = -1; 
        if (pos == n - 1) { 
            return true;
        }
        for (int i = 0; i < dx.length ; i++) { 
            int nx = x + dx[i], ny = y + dy[i];
            if (!(nx < 0 || nx >= m || ny < 0 || ny >= m || mp[nx][ny] != a[pos + 1])) {
                if (dfs(nx, ny, pos + 1, ans)) { 
                    return true;
                }
            }
        }
        mp[x][y] = gg; 
        for (int i = 0 ; i < 2 ; i++)
            ans.remove(ans.size() - 1); 
        return false; 
    }
    public static void readIn(){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); 
        a = new int[n]; 
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt(); 
        }
        m = sc.nextInt();
        mp = new int[m][m]; 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                mp[i][j] = sc.nextInt(); 
            }
        }
    	
    }
    public static void outPutList (List<Integer> arr){
        for (int k = 0; k < arr.size(); k++) {
            System.out.print(arr.get(k)); 
            if (k != arr.size() - 1) {
                System.out.print(" ");
            }
        }
    	return;
    }
    public static void main(String[] args) {
    	readIn();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                List<Integer> ans = new ArrayList<>();
                if (mp[i][j] == a[0] && dfs(i, j, 0, ans)) { 
                	outPutList(ans);
                    return;
                }
            }
        }
        System.out.println("error");
    }
}

Python

dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
def dfs(x, y, pos, ans):
    ans.append(x)
    ans.append(y)
    gg = mp[x][y]
    mp[x][y] = -1
    if pos == n - 1:
        return True
    for i in range(len(dx)):
        nx = x + dx[i]
        ny = y + dy[i]
        if not (nx < 0 or nx >= m or ny < 0 or ny >= m or mp[nx][ny] != a[pos + 1]):
            if dfs(nx, ny, pos + 1, ans):
                return True
    mp[x][y] = gg
    for i in range(2):
        ans.pop()
    return False

def readIn():
    global n, m, a, mp
    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    mp = []
    for i in range(m):
        row = list(map(int, input().split()))
        mp.append(row)

def outPutList(arr):
    for k in range(len(arr)):
        print(arr[k], end="")
        if k != len(arr) - 1:
            print(" ", end="")
    print()

readIn()
for i in range(m):
    for j in range(m):
        ans = []
        if mp[i][j] == a[0] and dfs(i, j, 0, ans):
            outPutList(ans)
            exit()
print("error")

JavaScript

const dx = [-1, 0, 0, 1];
const dy = [0, -1, 1, 0];
let n, m, a, mp;

function dfs(x, y, pos, ans) {
  ans.push(x);
  ans.push(y);
  const gg = mp[x][y];
  mp[x][y] = -1;
  if (pos === n - 1) {
    return true;
  }
  for (let i = 0; i < dx.length; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];
    if (!(nx < 0 || nx >= m || ny < 0 || ny >= m || mp[nx][ny] !== a[pos + 1])) {
      if (dfs(nx, ny, pos + 1, ans)) {
        return true;
      }
    }
  }
  mp[x][y] = gg;
  for (let i = 0; i < 2; i++) {
    ans.pop();
  }
  return false;
}

function readIn() {
  const lines = input.trim().split('\n');
  n = parseInt(lines[0]);
  a = lines[1].split(' ').map(Number);
  m = parseInt(lines[2]);
  mp = [];
  for (let i = 0; i < m; i++) {
    const row = lines[3 + i].split(' ').map(Number);
    mp.push(row);
  }
}

function outPutList(arr) {
  for (let k = 0; k < arr.length; k++) {
    process.stdout.write(arr[k].toString());
    if (k !== arr.length - 1) {
      process.stdout.write(' ');
    }
  }
  process.stdout.write('\n');
}

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
  input += data;
});
process.stdin.on('end', () => {
  readIn();
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < m; j++) {
      const ans = [];
      if (mp[i][j] === a[0] && dfs(i, j, 0, ans)) {
        outPutList(ans);
        process.exit();
      }
    }
  }
  console.log('error');
});

题目描述

有一种特殊的加密算法，明文为一段数字串，经过密码本查找转换，生成另一段密文数字串。规则如下 1.明文为一段数字串由0-9组成 2.密码本为数字0-9组成的二维数组 3.需要按明文串的数字顺序在密码本里找到同样的数字串，密码本里的数字串是由相邻的单元格数字组成，上下和左右是相邻的，注意:对角线不相邻，同一个单元格的数字不能重复使用。

4.每一位明文对应密文即为密码本中找到的单元格所在的行和列序号(序号从0开始)组成的两个数字。如明文第$i$位$Data[i]$对应密码本单元格为$Book[x][y]$，则明文第$i$位对应的密文为$XY$，$X$和$Y$之间用空格隔开

如果有多条密文，返回字符序最小的密文。如果密码本无法匹配，返回"error"

请你设计这个加密程序

示例1:

密码本:

[0 0 2]

[1 3 4]

[6 6 4]

明文:3,密文:“1 1”

示例2:

密码本:

0 0 2 ​ 1 3 4 ​ 6 6 4

明文:“0 3”,密文:“0 1 1 1”

输入描述

第一行输入1个正整数$N$,代表明文的长度$(1 \le N \le 200)$

第二行输入$N$个明文数字组成的序列$Data[i]$ (整数: $0 \le Data[i] \le 9$)

第三行1个正整数$M$,代表密文的长度

接下来$M$行，每行$M$个数，代表密文矩阵

输出描述

输出字典序最小密文.如果无法匹配，输出"error"

样例1

输入

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

输出

0 1 1 1

样例2

输入

2
0 5
3
0 0 2
1 3 4
6 6 4

输出

error

说明：找不到0 5的序列,返回error