-4

2 次元配列に関する割り当てが与えられます。次のように述べられています。

四角形の 2 次元 char grid [row] [col] と char 検索対象の a が与えられた場合、その char のすべてのオカレンスを含む最小の四角形を見つけ、その面積を返します。char が 1 回だけ出現する場合、それを囲む四角形は 1x1 で、面積は 1 です。文字が表示されない場合は、面積 0 を返します。
問題へのリンクと例: http ://www.stanford.edu/class/cs108/handouts081/03HW1CodeCamp.pdf (page 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

境界ボックスを見つける必要があります。

次のように想像してください。

マトリックスの両側 (上、下、左、右) に 1 つずつ、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

問題を分割します。あなたは何する必要があるの？

1.）左上隅を検出する必要があります2.）右下隅を検出する必要があります3.）その間のすべてが長方形です

これで、ネストのforループはcharArea、配列をループして左上から右下に形成されます。その特定の文字の2〜4回の発生を検出する必要があります。状況に応じて、rectのコーナーを完全に定義するために2文字、または1文字だけが必要です。

したがって、長方形の左上隅と右下隅がある場合、その大きさを計算することは問題にはなりません。

于 2012-07-13T15:31:27.407 に答える
0

問題は、コードから配列をどのように使用するかです。さて、あなたは変数の定義、特にクラス内の変数を探すことから始めるべきです。http://docs.oracle.com/javase/tutorial/java/javaOO/classes.htmlを読み始めることができます。これはフィールドと呼ばれ、グリッド宣言に使用しているものです...

于 2012-07-13T15:31:44.840 に答える
0

私がすることは、パラメータから char を取得し、最初に出現する文字を見つけ、それを int の 2 次元配列に格納して、座標のセットを保持することです。次に、逆方向に作業して、2 次元配列の最後から開始し、最後のオカレンスを見つけます。これは、それらが存在できる範囲を知っているためです。

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 に答える
0

ここでは、問題について考える方法をいくつか紹介します。

  1. この問題を鉛筆と紙でどのように解決しますか? 手で問題を解いたときに行った手順を分析し、それを論理的な手順に変換する方法を考えます。たとえば、子供に四角形を見つける方法を説明します。
  2. 基本的に、何かを「バインド」する方法を調べる場合は、長方形の最も端にある文字、つまり角にある文字を探す必要があります。一番左、一番上、一番右、一番下の位置を見つけると、長方形が定義されました。
于 2012-07-13T15:26:01.637 に答える