kaka-秘密の地図

3394 ワード
カカオ色 アルゴリズム#アルゴリズム# テキストリンク

質問する


ニオは秘密の地図を手に持って、プロドが普段私房のお金を隠している場所を教えた.しかし、この秘密地図はデジタル暗号化されており、位置を確認するために解読が必要です.幸いなことに、地図のパスワードを解読する方法が書かれたメモも見つかった.
  • 地図は、エッジ長nの正方形の配列形式であり、各セグメントは「空白」("")または「壁」("#")の2種類から構成されています.
  • 全図は、2つの地図を重ね合わせることによって得ることができる.それぞれ「地図1」と「地図2」と言います.地図1または地図2のいずれかが壁である部分は、地図全体でも壁である.地図1も地図2も空白の部分であり、地図全体においても空白である.
  • 「地図1」と「地図2」はそれぞれ整数配列で暗号化されている.
  • 暗号化された配列は、地図の各横線において、壁部分を1に符号化し、空白部分を0に符号化したときのバイナリ数の配列である.

    ニオがフロドの私房金を手に入れるために、秘密地図のパスワードを解読するのに役立つプログラムを作成しました.

    • 入力


    地図に入るエッジサイズnと2つの整数配列arr 1とarr 2を入力します.
  • 1 ≦ n ≦ 16
  • arr 1,arr 2は長さnの整数配列である.
  • 整数配列の各要素xがバイナリ数に変換されたときの長さはn以下である.すなわち、0≦x≦2^n–1を満たす.

    • しゅつりょく


    元の秘密地図を復号し、「#」と出力し、スペースの文字列配列を出力します.

    に答える


    KaKao Techブログで解説を見ながら解答していますが、この問題はビット演算を利用して解決した問題です.上の地図図によれば、nの大きさに一致するように、数字を2進数に変換し(一番前の位置が0であっても構わない)、2つの地図の2進数をor演算子として計算し、値が1の場合は#として出力し、値が0の場合は空白として出力する.
    この問題を解く際にstring変数とchar文字変数を用いた.
    9&(1<<3)の演算を出力すると8となる.
    01001&01000=01000

    コード#コード#

    #include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2)
{
	vector<string> answer = {};
	for (int i = 0; i < n; i++)
	{
		string res = "";
		char ch;
		for (int j = n - 1; j >= 0; j--) // 맨 앞자리부터 계산해야 하기 때문에 이처럼 반복문 사용
		{
			ch = ((arr1[i] & (1 << j)) || (arr2[i] & (1 << j))) ? '#' : ' ';
			res.push_back(ch);
		}
		answer.push_back(res);
	}
	return (answer);
}

// 테스트 케이스
int main()
{
	vector<int> arr1 = { 9, 20, 28, 18, 11 };
	vector<int> arr2 = { 30, 1, 21, 17, 28 };
	vector<string> res = solution(5, arr1, arr2);
	for (auto x : res)
		cout << x << "\n";
	return (0);
}
    npm (Node Package Manager)
    [Node.jsを一緒に学ぶ][009話]文章検索機能を追加