0 と 1 の行列があります。どのセルからでも始められます。可能なすべての 1 をカバーするために必要なステップ (上、下、左、右) の最小数を知りたいです。0からでも1からでも始められます。
例：
0 1 0
1 1 1
0 1 0
(2,2) から 1 ステップ以内ですべての 1 に到達できます。これを重み付けされていない無向グラフの隣接行列に関連付けます。基本的に、任意のポイントから開始できる場合は、最も遠い隣人を見つける必要があります。頂点だけから開始できれば、単純に BFS/DFS を使用してカウンターを保持することもできましたが、これは問題を引き起こします。
0/1 行列をグラフの隣接行列と考えることができますが、この特定のケースでは、すべてのノードが行列内のセルであり、各ノードがセルに直接隣接しているグラフが本当に重要です。マトリックスでそれに隣接します。
この問題を解決するための 1 つのオプションは、グラフ内の各ノードから開始して複数の幅優先検索を実行し、各ノードからグラフ内の任意の 1 までの最大距離を記録することです。次に、この最大距離を最小化するノードを選択できます。
私のアプローチは、開始セルから上下に広げ、各行でその行を両端に向かって広げ、これまでのステップ数を維持することです。
垂直方向または水平方向に移動することによって、開始点からセルまでのすべてのルートは、同じManhattan Distanceになります。
解決策、ここで試してください。
#include<stdio.h>
// test
int main (void)
{
int g[5][5] =
{
{ 1,0,0,0,0 },
{ 0,0,1,0,0 },
{ 0,1,1,1,1 },
{ 1,0,1,0,0 },
{ 0,0,0,1,0 }
};
printf("\n 4-way solution = %d \n", mmd4(5,5,g, 2,2));
printf("\n 8-way solution = %d \n", mmd8(5,5,g, 2,2));
return 0;
}
8ウェイソリューション
int mmd8(int h, int w, int g[h][w], int x, int y)
{
putchar('#');
return max8(mmd8_up (h,w,g,x-1,y ,1),
mmd8_down (h,w,g,x+1,y ,1),
mmd8_left (h,w,g,x ,y-1,1),
mmd8_right(h,w,g,x ,y+1,1),
mmd8_uleft (h,w,g,x-1,y-1,1),
mmd8_uright(h,w,g,x-1,y+1,1),
mmd8_dleft (h,w,g,x+1,y-1,1),
mmd8_dright(h,w,g,x+1,y+1,1));
}
int mmd8_up(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('U');
return max4(g[x][y]?steps:0,
mmd8_up (h,w,g,x-1,y ,steps+1),
mmd8_uleft (h,w,g,x-1,y-1,steps+1),
mmd8_uright(h,w,g,x-1,y+1,steps+1));
}
int mmd8_down(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('D');
return max4(g[x][y]?steps:0,
mmd8_down (h,w,g,x+1,y ,steps+1),
mmd8_dleft (h,w,g,x+1,y-1,steps+1),
mmd8_dright(h,w,g,x+1,y+1,steps+1));
}
int mmd8_left(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('L');
return max2(g[x][y]?steps:0,
mmd8_left (h,w,g,x ,y-1,steps+1),
mmd8_uleft(h,w,g,x-1,y-1,steps+1),
mmd8_dleft(h,w,g,x+1,y-1,steps+1));
}
int mmd8_right(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('R');
return max2(g[x][y]?steps:0,
mmd8_right (h,w,g,x ,y+1,steps+1),
mmd8_uright(h,w,g,x-1,y+1,steps+1),
mmd8_dright(h,w,g,x+1,y+1,steps+1));
}
int mmd8_uleft(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('W');
return max2(g[x][y]?steps:0,
mmd8_uleft(h,w,g,x-1,y-1,steps+1));
}
int mmd8_uright(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('X');
return max2(g[x][y]?steps:0,
mmd8_uright(h,w,g,x-1,y+1,steps+1));
}
int mmd8_dleft(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('Y');
return max2(g[x][y]?steps:0,
mmd8_dleft(h,w,g,x+1,y-1,steps+1));
}
int mmd8_dright(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('Z');
return max2(g[x][y]?steps:0,
mmd8_dright(h,w,g,x+1,y+1,steps+1));
}
4ウェイソリューション
int mmd4(int h, int w, int g[h][w], int x, int y)
{
putchar('#');
return max4(mmd_up (h,w,g,x-1,y ,1),
mmd_down (h,w,g,x+1,y ,1),
mmd_left (h,w,g,x ,y-1,1),
mmd_right(h,w,g,x ,y+1,1));
}
int mmd_up(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('U');
return max4(g[x][y]?steps:0,
mmd_up (h,w,g,x-1,y ,steps+1),
mmd_left (h,w,g,x ,y-1,steps+1),
mmd_right(h,w,g,x ,y+1,steps+1));
}
int mmd_down(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('D');
return max4(g[x][y]?steps:0,
mmd_down (h,w,g,x+1,y ,steps+1),
mmd_left (h,w,g,x ,y-1,steps+1),
mmd_right(h,w,g,x ,y+1,steps+1));
}
int mmd_left(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('L');
return max2(g[x][y]?steps:0,
mmd_left (h,w,g,x ,y-1,steps+1));
}
int mmd_right(int h, int w, int g[h][w], int x, int y, int steps)
{
if (base_case(h,w,x,y)) return 0;
putchar('R');
return max2(g[x][y]?steps:0,
mmd_right(h,w,g,x ,y+1,steps+1));
}
ユーティリティ機能
int base_case(int h, int w, int x, int y)
{
if (x < 0) return 1;
if (y < 0) return 1;
if (x >= h) return 1;
if (y >= w) return 1;
return 0;
}
int max2(int a, int b)
{
return ((a > b) ? a : b);
}
int max4(int a, int b, int c, int d)
{
int m = a;
if (b > m) m = b;
if (c > m) m = c;
if (d > m) m = d;
return m;
}
int max8(int a, int b, int c, int d, int e, int f, int g, int h)
{
int m = a;
if (b > m) m = b;
if (c > m) m = c;
if (d > m) m = d;
if (e > m) m = e;
if (f > m) m = f;
if (g > m) m = g;
if (h > m) m = h;
return m;
}