-4

我们得到一个关于 2-D 数组的赋值，其中指出：

给定一个矩形 2-d char grid [row] [col] 和 char 要查找的 a，找到包含该字符的所有出现的最小矩形并返回其面积。如果char只出现一次，那么包围它的矩形是1x1，面积是1。如果字符没有出现，则返回面积0。
这里是问题的链接和一个例子：http ://www.stanford.edu/class/cs108/handouts081/03HW1CodeCamp.pdf（第2页）但我们必须使用 int charArea (char[][] grid, char ch) 而不是 int charArea (char ch)

请帮我想出一个算法。我是 Java 新手，我很难想到伪代码/代码。我只知道

import java.util.*;

public class Area {

    public static int charArea (char[][] grid, char ch) {
        for (int i=0; i<3; i++) { //row
            for (int j=0; j<4; j++) { //column
            // What now, please?                        
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        char[][] grid = {
                {'a', 'b', 'c', 'd'},
                {'a', ' ', 'c', 'd'},
                {'x', 'b', 'c', 'a'}
        };
        Scanner input = new Scanner (System.in);
        System.out.print("Enter a character to look for: ");
        String temp = input.nextLine();
        char ch = temp.charAt(0);
        System.out.print(charArea(grid, ch));
    }

}

请帮我设计一个算法/伪代码（或代码，如果你不介意哈哈）。太感谢了！

4

6 回答 6

3

您需要找到一个边界框。

想象它是这样的：

您有 2 个垂直标尺和 2 个水平标尺，矩阵的每一侧（上、下、左和右）各一个。

拿起左边的垂直标尺并向右移动，直到你找到你要找的字母。
拿起右边的垂直标尺，向左移动，直到你找到你要找的字母。
拿起上面的水平尺并将其向下移动，直到找到您要查找的字母。
拿起较低的水平尺并将其向上移动，直到您找到要查找的字母。

完成后，4 个标尺将形成一个最小边界框。
剩下的就是数组中没有这样的字符的情况（提示：“右”标尺将离开“左”标尺）。

这是最基本的方法，可能不是最优的，但相当容易理解。:D

于 2012-07-13T15:29:44.257 回答
1

由于这是一项作业，我将向您提供您可能提出的基本想法your own solution：可以根据其四个角定义一个矩形。你可以找到这样的角落。请注意，最右边的出现ch，最左边的出现，顶部的和底部的会有所帮助，但它们不一定是角落！例如，左上角是(x,y)，其中x是最左边出现的行ch，并且y是最上面的列。

使用四个角的坐标，您可以定义包含ch矩阵中所有出现的最小矩形。

于 2012-07-13T15:26:37.880 回答
0

问题是：如何使用代码中的数组。好吧，你应该从寻找变量定义开始，特别是类中的变量。您可以开始阅读http://docs.oracle.com/javase/tutorial/java/javaOO/classes.html。它称为字段，这就是您用于网格声明的内容...

于 2012-07-13T15:31:44.840 回答
0

这里有几种方法来思考这个问题。

  1. 你会如何用铅笔和纸解决这个问题？分析您在手工解决问题时所经历的步骤，并思考如何将其转化为合乎逻辑的步骤，例如向孩子解释如何找到矩形。
  2. 本质上，如果您检查您是如何“绑定”某些内容的，您将需要在矩形的最远端（即角）处寻找字符。找到最左边、最上面、最右边和最下面的位置，您已经定义了一个矩形。
于 2012-07-13T15:26:01.637 回答
0

划分你的问题。你需要做什么？

1.) 你需要检测左上角 2.) 你需要检测右下角 3.) 中间的一切都是你的矩形

现在，嵌套的 for 循环charArea已经从左上角到右下角遍历数组。您必须检测该特定字符的 2-4 次出现。根据具体情况，您需要 2 个字符来完全定义矩形的一个角，或者只需要一个。

所以当你有矩形的左上角和右下角时，计算它有多大应该不是问题。

于 2012-07-13T15:31:27.407 回答
0

我要做的是从参数中获取字符并找到它的第一次出现，并将其存储在一个二维整数数组中以保存一组坐标。然后可能向后工作并从二维数组的末尾开始并找到最后一次出现，因为那时您知道它们可以在的范围内。

public static int charArea (char[][] grid, char ch) {
    int[] first = new int[2];
    int[] last = new int[2];
    for (int i=0; i<3; i++) { //row
        for (int j=0; j<4; j++) { //column
               //checks to see if it is the char we need
               if(grid[i][j].equals(ch) && (first[0] != null && first[1] != null)){
                  first[0] = i;
                  first[1] = j;
               }
        }
    }

    for (int i=3; i>0; i--) { //row
        for (int j=4; j>4; j--) { //column
           //checks to see if it is the char we need
               if(grid[i][j].equals(ch) && (first[0] != null && first[1] != null)){
                  last[0] = i;
                  last[1] = j;
               }                    
        }
    }

    answer = ((Math.max(first[0],last[0]) - Math.min(first[0],last[0])) *(Math.max(first[1],last[1]) - Math.min(fist[1],last[1]));

    return answer;
}
于 2012-07-13T15:50:54.237 回答