java - 在 char 数组中查找 'A' 的最长路径
问题描述
您好，非常感谢您的帮助！
我需要创建一个程序，该程序通过从文件中读取的 char 数组。然后程序需要使用递归来找到与当前'A'相邻（非对角线）的'A'的最长连续路径。它只能对每个“A”计数一次，因此一旦到达路径的尽头，它就不能倒退。我正在使用的示例字符数组是：
8 13
EAADDOAN
ATAFAWOB
ADAAAAIA
AWUYAAAA
ZAWAADDX
AAAAAAAZ
IMBAQJAA
AIAINOAK
AZVAJAAQ
VPNKAAAJ
TAAAWKAW
AAAAHRAV
ETEMAALA
Length of the longest A path is 23
8 表示列，13 表示数组的行。我已经设置了另一个布尔数组来跟踪是否已经计算了“A”。下面是遍历每个位置并调用递归函数的方法（看起来有点奇怪，第一次在这里发帖）：
public int findLongestPathLength() {
// TODO Auto-generated method stub
int i, j, x, y;
int numOfAs = 0;
int longestPath = 0;
// Create boolean array for checking if an 'A' has been counted or not
alreadyCounted = new boolean[numOfArrays][arrLength];
// Initialize all values in alreadyCounted array to false
for(i = 0; i < numOfArrays; i++) {
for(j = 0; j < arrLength; j++ ) {
alreadyCounted[i][j] = false;
}
}
for(i = 0; i < numOfArrays; i++) {
for(j = 0; j < arrLength; j++ ) {
if(map[i][j] == 'A') {
alreadyCounted[i][j] = true;
numOfAs = findPathLengthRecursive(i, j) + 1;
/* If this iteration of finding the longest path of 'A's is the longest
so far, replace the longestPath value with this number of A's */
if(numOfAs > longestPath)
longestPath = numOfAs;
// Initialize all values in alreadyCounted array back to false
for(x = 0; x < numOfArrays - 1; x++) {
for(y = 0; y < arrLength - 1; y++ ) {
alreadyCounted[x][y] = false;
}
}
// Reset currentLength in findPathLengthRecursive back to 0
currentLength = 0;
}
}
}
return longestPath;
}
我创建的递归方法是： public int findPathLengthRecursive(int i, int j) { // TODO 自动生成的方法存根
// To check if there is an 'A' to any of the sides of the current cell
boolean left = true, right = true, up = true, down = true;
/* Base case (when recursion should stop) is when there is no 'A's left to count in the path */
if(j == 0 || (j > 0 && (map[i][j - 1] != 'A' || alreadyCounted[i][j - 1]))){
left = false;
}
if(j == arrLength - 1 || (j < arrLength - 1 && (map[i][j + 1] != 'A' || alreadyCounted[i][j + 1]))) {
right = false;
}
if(i == numOfArrays - 1 || (i < numOfArrays - 1 && (map[i + 1][j] != 'A' || alreadyCounted[i + 1][j]))) {
down = false;
}
if(i == 0 || (i > 0 && (map[i - 1][j] != 'A' || alreadyCounted[i - 1][j]))) {
up = false;
}
// If there is no valid 'A's around then return currentLength
if(!left && !right && !down && !up) {
return currentLength;
} else {
if(down && left && up && right) {
alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
currentLength += Math.max(Math.max(Math.max(findPathLengthRecursive(i + 1, j), findPathLengthRecursive(i, j - 1)), findPathLengthRecursive(i - 1, j)), findPathLengthRecursive(i, j + 1));
}
else if(left && up && right) {
alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
currentLength += Math.max(Math.max(findPathLengthRecursive(i, j - 1), findPathLengthRecursive(i - 1, j)), findPathLengthRecursive(i, j + 1));
}
else if(up && right && down) {
alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
currentLength += Math.max(Math.max(findPathLengthRecursive(i - 1, j), findPathLengthRecursive(i, j + 1)), findPathLengthRecursive(i + 1, j));
}
else if(right && down && left) {
alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
currentLength += Math.max(Math.max(findPathLengthRecursive(i, j + 1), findPathLengthRecursive(i + 1, j)), findPathLengthRecursive(i, j - 1));
}
else if(down && left && up) {
alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
currentLength += Math.max(Math.max(findPathLengthRecursive(i + 1, j), findPathLengthRecursive(i, j - 1)), findPathLengthRecursive(i - 1, j));
}
else if(left && right) {
alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
currentLength += Math.max(findPathLengthRecursive(i, j - 1), findPathLengthRecursive(i, j + 1));
}
else if(up && down) {
alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
currentLength += Math.max(findPathLengthRecursive(i - 1, j), findPathLengthRecursive(i + 1, j));
}
else if(left && up) {
alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
currentLength += Math.max(findPathLengthRecursive(i, j - 1), findPathLengthRecursive(i - 1, j));
}
else if(left && down) {
alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
currentLength += Math.max(findPathLengthRecursive(i, j - 1), findPathLengthRecursive(i + 1, j));
}
else if(right && up) {
alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
currentLength += Math.max(findPathLengthRecursive(i, j + 1), findPathLengthRecursive(i - 1, j));
}
else if(right && down) {
alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
currentLength += Math.max(findPathLengthRecursive(i, j + 1), findPathLengthRecursive(i + 1, j));
}
else if(left) {
currentLength++;
alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
findPathLengthRecursive(i, j - 1);
}
else if(up) {
currentLength++;
alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
findPathLengthRecursive(i - 1, j);
}
else if(right) {
currentLength++;
alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
findPathLengthRecursive(i, j + 1);
}
else if(down) {
currentLength++;
alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
findPathLengthRecursive(i + 1, j);
}
}
return currentLength;
}
无论我尝试什么，它似乎只是返回不接近我正在寻找的 23 的随机数。
这是从第一个方法调用递归方法时的输出。
136 70 1 3 70 58 1 56 70 36 37 1 3 60 53 69 85 66 69 85 66 54 43 63 51 49 79 84 109 142 2 1 139 2 1 87 116 119 118 06 132 3 2 4 13 16 132 3 2 4 13 16 1 1 166
任何帮助都会非常有帮助，谢谢！
解决方案
char [][]mat;
boolean visit[][];
int rowSize , columnSize;
int dx[] = {-1 , 0 , 0 , +1};
int dy[] = { 0 , +1 , -1 , 0};
int rec(int row , int col){
visit[row][col] = true;
int ret = 0;
for(int k = 0 ; k < 4 ; ++k){
int nr = row+dx[k];
int nc = col+dy[k];
if(nr < 0 || nr >= rowSize || nc < 0 || nc >= columnSize || visit[nr][nc] && mat[nr][nc] != 'A'){
continue;
}
ret += 1 + rec(nr , nc);
}
return ret;
}
void main(){
//todo input the matris and rowSize , columnSize
//todo make all item of visit by 0;
int mx = 0;
for(int i = 0 ; i < rowSize; ++i){
for(int j = 0 ; j < columnSize; ++j){
int cur = rec(i ,j);
mx = mx > cur ? mx : cur;
}
}
//mx is answer
}
推荐阅读
- javascript - 我们可以在 JS 文件的顶部写“use strict”，它会验证所有函数和语句吗？
- python - Django Migration InternalError 1054 未知列
- c - 使用 SAT 求解器打印 N-Queens 问题的所有解
- vue.js - 将 Axios 调用的结果添加到 State
- javascript - 带有数据表的嵌套表
- python - MySQL/python 字符集问题
- r - 从第三次观察开始，在 R 中进行黄土曲线拟合
- scala - 没有参数评估 zeppelin 中定义的 Scala 方法
- python - 如何基于单个列上的多个 StringMethods 有效且惯用地过滤 PandasDF 行？
- linux-kernel - 在 5.4 中编译 gpio-mockup