题目
思路分析
抽象题意
题目的模型是一个很经典的模型,就是匹配单词
但是在匹配单词的基础上追加了一个加密的过程
概括题目的意思其实就是给定一个加密后的矩阵,求出单词映射匹配后、在八个方向上满足MOO格式的单词个数(加密映射的方式随意,但是不可以原地TP,并且不会出现多个单词映射到同一个单词的情况)
具体实现
我们其实无须关心具体要如何匹配他的映射关系,针对矩阵中的每一个点,我们都去八个方向上枚举可能出现的MOO
如果出现了MOO的情况,我们就记录,这里具体的记录可以用一个Map来存储,比如加密后的ABB/ACC这种,我们的Map定义如下:
Map<String,Integer> map = new Hashmap<>() // 类似比如(AB,1)
我们遍历棋盘中的每一个点,然后每个点都去八个方向再枚举可能出现的MOO,记录的时候以MOO中的MO作为key,value为出现的个数
最后统计一下每个key对应的value,求出最大值
代码实现
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
/**
* @author HuangSir
* @date 2022-05-01 9:49
*/
public class Main
{
static int n;
static int m;
static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
static int[] dy = {1, 1, 0, -1, -1, -1, 0, 1};
static Map<String, Integer> map = new HashMap<>();
public static void main(String[] args)
throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] head = reader.readLine().split(" ");
n = Integer.parseInt(head[0]);
m = Integer.parseInt(head[1]);
String[] board = new String[n];
for (int i = 0; i < n; i++) {
board[i] = reader.readLine();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
count(i, j, board);
}
}
int res = 0;
for (String key : map.keySet()) {
//不可以映射到自己
if (key.charAt(1) == 'O') {
continue;
}
res = Math.max(res, map.get(key));
}
System.out.println(res);
}
private static void count(int i, int j, String[] board)
{
//枚举八个方向
for (int k = 0; k < 8; k++) {
//第一个O
int x1 = i + dx[k];
int y1 = j + dy[k];
//第二个O
int x2 = x1 + dx[k];
int y2 = y1 + dy[k];
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && x2 >= 0 && x2 < n && y2 >= 0 && y2 < m) {
if (board[x1].charAt(y1) == board[x2].charAt(y2) && board[i].charAt(j) != board[x1].charAt(y1)) {
StringBuilder sb = new StringBuilder();
sb.append(board[i].charAt(j));
sb.append(board[x1].charAt(y1));
map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) + 1);
}
}
}
}
}