グリッドに数字ハイフネーションを貼り付ける
SW Expert D 4問題メッシュでのデジタル接続問題
4×4つの大きさの格子板があります.格子板の各格子には0から9の数字が書かれています.
格子板の任意の位置から東、西、北の4方向に隣接する格子に6回移動し、各格子の数字を順番に貼り付けると7桁になります.
移動時には、一度通過したメッシュを再通過したり、0から始まる0102001と同じ数を作成したりすることができます.
ただし、グリッドの外に移動することはできないとします.
メッシュが指定されている場合は、作成可能な7つの異なる桁数の個数を求めるプログラムを作成します.
Input:
1
1 1 1 1
1 1 1 2
1 1 2 1
1 1 1 1
Output:
#1 23
上記の質問に答えました.
Setを利用すると簡単に解けます.
グローバル変数の使用を避けるために、できるだけ変数と内容をパラメータに渡します.
Headerは以下の内容を順調に完成しました.Directionはそのまま東西南北をpairlistとして保存
次は小切手です.正直に言って、私はずっとMemoizationを使うことを考えていますが、すべての1~6個の数字を保存するのは難しいです.
考えてみれば、4方向の7位は4^7、2^14、多分で十分、2秒なら時間に余裕があるでしょうから、帰りだけはちゃんと書くことにしました.
(length=7このときは戻らなかったので10分ほどウロウロしました.
幸いtest case for文で宣言したので気にしないでください.
Easy
4×4つの大きさの格子板があります.格子板の各格子には0から9の数字が書かれています.
格子板の任意の位置から東、西、北の4方向に隣接する格子に6回移動し、各格子の数字を順番に貼り付けると7桁になります.
移動時には、一度通過したメッシュを再通過したり、0から始まる0102001と同じ数を作成したりすることができます.
ただし、グリッドの外に移動することはできないとします.
メッシュが指定されている場合は、作成可能な7つの異なる桁数の個数を求めるプログラムを作成します.
Input:
1
1 1 1 1
1 1 1 2
1 1 2 1
1 1 1 1
Output:
#1 23
上記の質問に答えました.
Setを利用すると簡単に解けます.
グローバル変数の使用を避けるために、できるだけ変数と内容をパラメータに渡します.
Headerは以下の内容を順調に完成しました.Directionはそのまま東西南北をpairlistとして保存
#include <iostream>
#include <set>
#include <string>
using namespace std;
pair<int, int> directions[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; //to check adjcent
私は主にBoundaryバッグが好きです.本来は負数の正数に分けるために-1で埋めたのですが、後で忘れてしまい、再び限界を画定しました.何の関係もない次は小切手です.正直に言って、私はずっとMemoizationを使うことを考えていますが、すべての1~6個の数字を保存するのは難しいです.
考えてみれば、4方向の7位は4^7、2^14、多分で十分、2秒なら時間に余裕があるでしょうから、帰りだけはちゃんと書くことにしました.
(length=7このときは戻らなかったので10分ほどウロウロしました.
void check(int **array, int i, int j, string st, set<string> *set_name)
{
if (i == 0 || i == 5 || j == 0 || j == 5) //out of boundary
return;
st = st + to_string(array[i][j]);
if (st.length() == 7) //found seven
{
set_name->insert(st);
return;
}
for (int k = 0; k < 4; k++)
check(array, i + directions[k].first, j + directions[k].second, st, set_name);
}
他の人はSetを初期化していないので時間を無駄にしたと言っています.グローバル言語で作られたからかもしれません.幸いtest case for文で宣言したので気にしないでください.
Easy
int main(int argc, char **argv)
{
int sum = 0;
int test_case;
int T;
cin >> T;
int **arr = new int *[6];
for (int i = 0; i < 6; i++)
arr[i] = new int[6];
for (test_case = 1; test_case <= T; ++test_case)
{
set<string> ans;
//input with padding -1
for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 6; j++)
{
if (i == 0 || i == 5 || j == 0 || j == 5)
arr[i][j] = -1;
else
cin >> arr[i][j];
}
}
//do I need memoization? I don't think so
for (int i = 1; i < 5; i++)
for (int j = 1; j < 5; j++)
check(arr, i, j, "", &ans);
cout << "#" << test_case << " " << ans.size() << endl;
}
for (int i = 0; i < 6; i++)
delete[] arr[i];
delete[] arr;
return 0; //정상종료시 반드시 0을 리턴해야합니다.
}
BReference
この問題について(グリッドに数字ハイフネーションを貼り付ける), 我々は、より多くの情報をここで見つけました https://velog.io/@twoyearsone/문제풀이swacademy격자판에숫자이어붙이기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol