ロボットがグリッド内を移動するために必要な総コストを調べるためのC++プログラム
次元hxwのグリッドが与えられていると仮定します。グリッド内の各セルには、正の整数が含まれています。これで、特定のセル(p、q)(pはセルの行番号、qはセルの列番号)にパスファインディングロボットが配置され、セル(i、j)に移動できます。移動操作には、| p--i|に等しい特定のコストがあります。 + | q--j|。現在、q回のトリップがあり、次のプロパティがあります。
-
各トリップには2つの値(x、y)があり、共通の値dがあります。
-
ロボットが値xのセルに配置され、値x+dの別のセルに移動します。
-
次に、値x + d+dを持つ別のセルに移動します。このプロセスは、ロボットがy以上の値を持つセルに到達するまで続きます。
-
y-xはdの倍数です。
旅行を考えると、各旅行の総費用を調べる必要があります。ロボットが動かない場合、旅費は0です。
したがって、入力がh =3、w =3、d =3、q =1、grid ={{2、6、8}、{7、3、4}、{5、1、9}}のような場合、trips ={{3、9}}の場合、出力は4になります。
3はセル(2、2)にあります
6はセル(1、2)にあります
9はセル(3、3)にあります
総コスト=|(1-2)+(2-2)| + |(3-1)+(3-2)| =4.
これを解決するには、次の手順に従います-
Define one map loc for initialize i := 0, when i < h, update (increase i by 1), do: for initialize j := 0, when j < w, update (increase j by 1), do: loc[grid[i, j]] := new pair(i, j) Define an array dp[d + 1] for initialize i := 1, when i <= d, update (increase i by 1), do: j := i while j < w * h, do: n := j + d if j + d > w * h, then: Come out from the loop dx := |first value of loc[n] - first value of loc[j]| dy := |second value of loc[n] - second value of loc[j]| j := j + d insert dx + dy at the end of dp[i] for initialize j := 1, when j < size of dp[i], update (increase j by 1), do: dp[i, j] := dp[i, j] + dp[i, j - 1] for initialize i := 0, when i < q, update (increase i by 1), do: tot := 0 le := first value of trips[i] ri := second value of trips[i] if ri mod d is same as 0, then: f := d Otherwise, f := ri mod d pxl := (le - f) / d pxr := (ri - f) / d if le is same as f, then: if ri is same as f, then: tot := 0 Otherwise tot := tot + (dp[f, pxr - 1] - 0) Otherwise if ri is same as f, then: tot := 0 Otherwise tot := tot + dp[f, pxr - 1] - dp[f, pxl - 1] print(tot)
理解を深めるために、次の実装を見てみましょう-
例
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; void solve(int h, int w, int d, int q, vector<vector<int>> grid, vector<pair<int, int>> trips) { map<int, pair<int, int>> loc; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) loc[grid[i][j]] = make_pair(i, j); } vector<int> dp[d + 1]; for (int i = 1; i <= d; i++) { int j = i; while (j < w * h) { int n = j + d; if (j + d > w * h) break; int dx = abs(loc[n].first - loc[j].first); int dy = abs(loc[n].second - loc[j].second); j += d; dp[i].push_back(dx + dy); } for (j = 1; j < dp[i].size(); j++) dp[i][j] += dp[i][j - 1]; } for (int i = 0; i < q; i++) { int tot = 0; int le, ri; le = trips[i].first; ri = trips[i].second; int f; if (ri % d == 0) f = d; else f = ri % d; int pxl, pxr; pxl = (le - f) / d; pxr = (ri - f) / d; if (le == f){ if (ri == f) tot = 0; else tot += (dp[f][pxr - 1] - 0); } else { if (ri == f) tot = 0; else tot += dp[f][pxr - 1] - dp[f][pxl - 1]; } cout<< tot << endl; } } int main() { int h = 3, w = 3, d = 3, q = 1; vector<vector<int>> grid = {{2, 6, 8}, {7, 3, 4}, {5, 1, 9}}; vector<pair<int, int>> trips = {{3, 9}}; solve(h, w, d, q, grid, trips); return 0; }
入力
3, 3, 3, 1, {{2, 6, 8}, {7, 3, 4}, {5, 1, 9}}, {{3, 9}}
出力
4
-
グリッド内の照らされたセルの数を見つけるためのC++プログラム
次元h*wのグリッドが与えられていると仮定します。グリッド内のセルには、球根または障害物のいずれかを含めることができます。電球のセルはそれ自体とその右、左、上、下のセルを照らし、障害物のセルが光を遮らない限り、光はセルを通して輝くことができます。障害物セルは照明できず、電球セルからの光が他のセルに到達するのを防ぎます。したがって、配列「bulb」内のグリッド内の電球セルの位置と配列「obstacles」内の障害物セルの位置を考えると、照らされているグリッド内のセルの総数を見つける必要があります。 したがって、入力がh =4、w =4、bulb ={{1、1}、{2、2}、{3、3}}、障害物
-
パスを作成するためにグリッドでブロックするセルの数を見つけるためのC++プログラム
次元h*wのグリッドがあるとします。セル位置(0、0)にロボットがあり、その位置(h-1、w-1)に移動する必要があります。グリッドには、ブロックされたセルとブロックされていないセルの2種類のセルがあります。ロボットはブロックされていないセルを通過できますが、ブロックされたセルを通過することはできません。ロボットは4つの方向に進むことができます。左、右、上、下に移動できます。ただし、ロボットはセルから別のセルに任意の方向に移動する可能性があるため(前のセルを無視して)、1つのパスのみを作成し、そのパスにない他のすべてのセルをブロックする必要があります。 (0、0)から(h -1、w -1)まで