题目:
题解:
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
typedef struct{int x;int y;
}coordinate;//坐标结构体int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes){int dx[4]={-1,0,1,0};//用作坐标偏移int dy[4]={0,-1,0,1};//新建队列,存放坐标数组coordinate* queue=(coordinate*)malloc(sizeof(coordinate) * 10240);int front=0;int rear=0;//设置结果数组返回值*returnSize=matSize;*returnColumnSizes=matColSize;//returnColumnSizes是一个二级指针,解引用之后是一个一级指针,可以直接等于//定义二级指针,申请空间构建二维数组当结果int** result=(int**)malloc(sizeof(int*) * matSize);//申请matSize个空间存储每一个行指针for(int i=0;i<matSize;i++){//result[i]=(int*)malloc(sizeof(int) * (*matColSize)); *(result+i)=(int*)malloc(sizeof(int) * (*matColSize));//给行指针申请*matColSize个空间//初始化二维数组--原数组为0的地方初始化为0,为1的地方初始化化为max,方便后面进行距离比较for(int j=0;j<*matColSize;j++){if(mat[i][j]==0){result[i][j]=0;queue[rear].x=i;queue[rear].y=j;//将该坐标入队rear++;//队尾指针后移一位,指向空}else{result[i][j]=INT_MAX;//INT_MAX --> 整数类型所能表达的最大值}}}//开始进行广度优先搜索int x,y;//扩散后的坐标while(front!=rear){for(int i=0;i<4;i++){x=queue[front].x+dx[i];y=queue[front].y+dy[i];if(x>=0 && x<matSize && y>=0 && y<*matColSize){//result[x][y]为INT_MAX的时候if(result[x][y] > result[queue[front].x][queue[front].y]+1){result[x][y] = result[queue[front].x][queue[front].y]+1;queue[rear].x=x;//将新的已经被赋值所求距离的位置坐标入队queue[rear].y=y;rear++;}}}front++;//队列头指针后移,接着往后遍历}return result;
}