[実施]新ゲーム2 boj 17837

25228 ワード
boj 17837 boj C サムスンソフトウェアアルゴリズム インプリメンテーション algorithm cpp 新しいゲーム2 テキストリンク

  • 17837
    https://www.acmicpc.net/problem/17837





  • アルゴリズム問題では,初めて構造体を構築して用いた.

  • 移動や方向変更などの作業は配列対応が望ましい.

  • 自分では思い出せない方法
    int turn_d[5] = {0, 2, 1, 4, 3};

d = turn_d[d];
    方向を変えるときに、このように既存のindexを入れて、変えたいindexを突き出した位置に並べると、簡単に変えられます.
    if (d == 1)
	d = 2
else if (d == 2)
	d = 1
else if (d == 3)
	d = 4
else if (d == 4)
	d = 3

이런 수고를 덜어줄 수 있다는 뜻이다.

  • 特に,今回学習した逆方向,find関数を使えば,より便利になる.
  • find関数を使用して、ベクトル内の要素の位置を指すポインタを受信できます.
  • ポインタを使用すると、特定のインデックスの位置から位置に逆方向に移動できます.
  • はまた、eraseによって範囲内の要素をすべて消去することもできる.
  • 実際にPythonを使用すると、これは非常に容易になります.

  • またfindで検索したポインタのtypeは自動的に指定でき、データ型を容易に指定できます.
    auto it = find(cur.begin(), cur.end(), i);

이 코드는 아래와 상동이다.

vector<int>::iterator it = find(cur.begin(), cur.end(), i);

  • ある要素を処理するときに、referenceを&で呼び出すと、コードの可読性が向上するだけでなく、コンパイル速度も速くなります.
    vector<int>& cur = st[h[i].y][h[i].x];

이런식으로 &로 해두면 사본이 아닌 원본을 참조하기 때문에
cur를 조정하면 st안에있는 내용이 바뀌게 된다.

  • また、関数の戻り値がある値より大きいか否かを判別するために、関数の戻り値をその値とすることができ、容易に判断することができる.

  • すなわち、一度移動すると、その座標の要素の個数が返され、座標の要素の個数を変更して所望の条件と比較することができる.
    int move(int i)
{
	...

return (next.size());
}

if (move(i) >= 4)
	...

    コード#コード#

    #include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct horse
{
	int x, y, d;
}		h[11];
int N, K;
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, -1, 1};
int maps[14][14];
int turn_d[5] = {0, 2, 1, 4, 3};
vector<int> st[14][14];

int move(int i)
{
	int ny = h[i].y + dy[h[i].d];
	int nx = h[i].x + dx[h[i].d];
	if (ny > N || nx > N || nx <= 0 || ny <= 0 || maps[ny][nx] == 2)
	{
		h[i].d = turn_d[h[i].d];
		ny = h[i].y + dy[h[i].d];
		nx = h[i].x + dx[h[i].d];
		if (ny > N || nx > N || nx <= 0 || ny <= 0 || maps[ny][nx] == 2)
			return (0);
	}
	vector<int>& cur = st[h[i].y][h[i].x];
	vector<int>& next = st[ny][nx];

	auto it = find(cur.begin(), cur.end(), i);

	if (maps[ny][nx] == 1)
		reverse(it, cur.end());
	for (auto m = it; m != cur.end(); m++)
	{
		h[*m].x = nx;
		h[*m].y = ny;
		next.push_back(*m);
	}
	cur.erase(it, cur.end());
	return (next.size());
}

int main(void)
{
	cin >> N >> K;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> maps[i][j];
	for (int i = 1; i <= K; i++)
	{
		cin >> h[i].y >> h[i].x >> h[i].d;
		st[h[i].y][h[i].x].push_back(i);
	}
	for (int count = 1; count <= 1000; count++)
	{
		for (int i = 1; i <= K; i++)
		{
			if (move(i) >= 4)
			{
				cout << count << endl;
				return (0);
			}
		}
	}
	cout << "-1" << endl;
	return (0);
}
    • [TIL-20210604] What is React?
    HackerRank | Sorting - Quicksort 1