matrix - 邻接矩阵邻居

Question

我有一个 0 和 1 的矩阵。我可以从任何单元格开始。我想知道覆盖所有可能的 1 所需的最小步数（上、下、左、右）是多少。我可以从 0 或 1 开始。

例子：

0 1 0 
1 1 1
0 1 0

在 1 步内从 (2,2) 开始，我可以达到所有 1。我将此与未加权无向图的邻接矩阵联系起来。本质上，当我可以从任何点开始时，我需要找到最远的邻居。如果我只能从顶点开始，我可以简单地使用 BFS/DFS 并保留一个计数器，但这会带来问题。

Answer 1

虽然您可以将 0/1 矩阵视为某些图的邻接矩阵，但在这种特殊情况下，您真正​​关心的图是每个节点都是矩阵中的一个单元且每个节点直接与单元相邻的图在矩阵中与之相邻。

解决此问题的一种选择是运行多个广度优先搜索，从图中的每个节点开始，并记录从每个节点到图中任意 1 的最大距离。然后，您可以选择最小化此最大距离的节点。

Answer 2

我的方法是从起始单元格向上和向下传播，然后在每一行上通过该行向两端传播，保持到目前为止所采取的步数。

从起点到单元的所有路线，通过垂直或水平移动，将产生相同的曼哈顿距离。

解决方案，在这里尝试。

#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;
}