[Algorithm] 🤞白駿3005クロスワードパズルを見る

23458 ワード
白駿 インプリメンテーション テキストリンク

0、問題


クロスワードパズルはR*Cサイズの矩形で構成され、各格子は空またはブロックされています.パズルは、水平(左->右)または垂直(上->下)の連続するスペースで空白を埋めます.
東ヒョクはクロスワードパズルをしない彼は緩んだパズルを見ていた.そして、彼はそのパズルの中で辞書の順番で一番前の単語を探した.△単語は少なくとも2文字です.
クロスワードパズルがある場合は、一番前の単語を辞書順に出力するプログラムを作成します.
入力
第1行は、RおよびC(2≦R,C≦20)を与える.Rは行の個数、Cは列の個数である.次のR行にはC文字が含まれます.各文字は英字小文字または「#」で、「#」の場合はブロックされます.
しゅつりょく
最初の行は辞書順に最初の単語を出力します.正しい答えが常に存在する場合にのみ、入力が与えられます.

1.アイデア


💡 水平(左→右)が2文字以上の単語を検索しlistに保存
💡 垂直(上→下)2文字以上の単語を検索してリストに保存
💡 昇順で単語リストを並べて最初の単語を出力

2.コア解答


文字数が2文字より大きい単語
  • (左から右)を検索し、リスト
    • に保存します.
    for(int i=0; i<r; i++) {
	String tmp = "";
	length = 0;
	for(int j=0; j<c; j++) {
		if(cross[i][j].equals("#")) {
			if(length >= 2) {
				list.add(tmp);
			}
			length = 0;
			tmp = "";
		} else {
			tmp += cross[i][j];
			length++;
		}
	}
	if(tmp.length() >= 2)
		list.add(tmp);
}
  • 歳(上から下へ)、2文字以上の単語を検索しlistに保存する
    • 歳
    for(int i=0; i<c; i++) {
	String tmp = "";
	length = 0;
	for(int j=0; j<r; j++) {
		if(cross[j][i].equals("#")) {
			if(length >= 2) {
				list.add(tmp);
			}
			length = 0;
			tmp = "";
		} else {
			tmp += cross[j][i];
			length++;
		}
	}
	if(tmp.length() >= 2)
		list.add(tmp);
}
  • 個の単語を含むリストを昇順に並べ、最初の単語
    • を出力する.
    Collections.sort(list);

    3.コード

    import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
public class Imple_12 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		
		int r = Integer.parseInt(s[0]);
		int c = Integer.parseInt(s[1]);
		
		String [][] cross = new String[r][c];
		ArrayList<String> list = new ArrayList<String>();
		
		for(int i=0; i<r; i++) {
			s = br.readLine().split("");
			for(int j=0; j<c; j++) {
				cross[i][j] = s[j];
			}
		}
		
		int length = 0;
		
		for(int i=0; i<r; i++) {
			String tmp = "";
			length = 0;
			for(int j=0; j<c; j++) {
				if(cross[i][j].equals("#")) {
					if(length >= 2) {
						list.add(tmp);
					}
					length = 0;
					tmp = "";
				} else {
					tmp += cross[i][j];
					length++;
				}
			}
			if(tmp.length() >= 2)
				list.add(tmp);
		}
		
		for(int i=0; i<c; i++) {
			String tmp = "";
			length = 0;
			for(int j=0; j<r; j++) {
				if(cross[j][i].equals("#")) {
					if(length >= 2) {
						list.add(tmp);
					}
					length = 0;
					tmp = "";
				} else {
					tmp += cross[j][i];
					length++;
				}
			}
			if(tmp.length() >= 2)
				list.add(tmp);
		}
		
		Collections.sort(list);
		
		System.out.println(list.get(0));
	}

}

    4.結果



    成功
    スタイルシート、XSL
    🔥TIL#11. AWSへのサービスの導入