Manchester-水陆距离 (朴素方法)

解题思路:

①：若某陆地上下左右其中有一个是水域，则该陆地到水域的最短距离一定为1

②：两个点的距离为x坐标相减的差得绝对值与y坐标相减差的绝对值之和

③：把所有水域的坐标保存起来，用②距离公式求出距离选最小一个

④：输出结果

注意事项:

题目输入的格式是以字符输入

参考代码:

#include<stdio.h>
#include<malloc.h>
#include<math.h>
/*存放水域坐标*/
typedef struct Waterlist_{
   int x;
   int y;

}*waterlist,Waterlist;

/*整个水陆结构体*/
typedef struct DMap_{
  int **data;/*水陆矩阵*/
  int length;/*水域坐标数组长度*/
  waterlist WList;/*水域坐标结构体数组*/

}*dmap,DMap;

void creat_Dmap(int N,int M,dmap R);/*创建水陆矩阵，及水域坐标*/
void get_minD(int N,int M,dmap R);/*求每个陆地距离最近水域的距离*/
void out_put(int N,int M,dmap R);/*输出结果*/
void freespace(int N,int M,dmap R);/*释放空间*/
/*-----------------------------------------------------------------------------*/
int main()
{
    /*N行，M列*/
   int N,M;
   DMap R;

while(scanf("%d%d",&N,&M)!=EOF)
{

       /*创建水陆矩阵，及水域坐标*/
      creat_Dmap(N,M,&R);
      /*求每个陆地距离最近水域的距离*/
      get_minD(N,M,&R);
      /*输出结果*/
      out_put(N,M,&R);
      /*释放空间*/
      freespace(N,M,&R);
 }
   return 0;
}
/*-----------------------------------------------------------------------------*/
void creat_Dmap(int N,int M,dmap R)/*创建水陆矩阵，及水域坐标*/
{
    /*开辟二维数组空间*/
    R->data=(int **)malloc(N*sizeof(int *));
    for(int i=0;i<N;i++)
        R->data[i]=(int *)malloc(M*sizeof(int));

    /*初始化水域坐标数组长度*/
    R->length=0;
    /*输入数据*/
    char ch[M+1];
    getchar();

    for(int i=0;i<N;i++)
    {
        scanf("%s",ch);
        for(int j=0;j<M;j++)
        {
            R->data[i][j]=ch[j]-'0';
            /*是水域水域数组长度加1*/
            if(R->data[i][j]==0)
                R->length++;
        }

    }
        /*开辟水域数组空间*/
        R->WList=(waterlist)malloc(R->length*sizeof(Waterlist));
        /*保存水域坐标*/
        int t=0;
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
        {
            if(R->data[i][j]==0)
            {
                R->WList[t].x=i;
                R->WList[t].y=j;
                t++;
            }
        }

return ;
}
/*-----------------------------------------------------------------------------*/
void get_minD(int N,int M,dmap R)/*求每个陆地距离最近水域的距离*/
{
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
    {
        if(R->data[i][j]==1)
        {
            /*是陆地*/
            /*看其临近上下左右是否有水域，有则水域距离直接设置为1*/
            if(i-1>=0&&R->data[i-1][j]==0) //上边
            {
                R->data[i][j]=1;
            }else
            if(i+1<N&&R->data[i+1][j]==0) //下边
            {
                R->data[i][j]=1;
            }else
            if(j-1>=0&&R->data[i][j-1]==0) //左边
            {
                R->data[i][j]=1;
            }else
            if(j+1<M&&R->data[i][j+1]==0) //右边
            {
                R->data[i][j]=1;
            }else
            /*若其临近的上下左右都没有水域，则求两点间距离*/
            {
                int mind;/*最小距离*/
                /*更具题目路径距离只能横着或竖着走，故两点间距离为两点的x，y坐标分别相减的绝对值再求和*/
                mind=fabs(i-R->WList[0].x)+fabs(j-R->WList[0].y);
                 for(int k=1;k<R->length;k++)
                 {
                     if(mind>fabs(i-R->WList[k].x)+fabs(j-R->WList[k].y))
                        mind=fabs(i-R->WList[k].x)+fabs(j-R->WList[k].y);
                 }
                 /*存入最短距离*/
                 R->data[i][j]=mind;
            }
        }
    }
    return ;
}
/*-----------------------------------------------------------------------------*/
void out_put(int N,int M,dmap R)/*输出结果*/
{
        for(int i=0;i<N;i++)
        {
             for(int j=0;j<M;j++)
                printf("%d ",R->data[i][j]);
             printf("\n");
        }
}
/*-----------------------------------------------------------------------------*/
void freespace(int N,int M,dmap R)/*释放空间*/
{
    for(int i=0;i<N;i++)
        free(R->data[i]);
    free(R->data);
    free(R->WList);
}

方法朴素，喜欢点个赞-.-