华为机试(污水污染）

给一个二维数组，污染源为1，干净水源为0，每隔一天污染源向相邻的上下左右扩散一格，求多少天全部污染？

example： 1 0

0 0

输出 ： 2天

代码：

#include"stdafx.h"

#include<stdio.h>

#include<malloc.h>

//污水行

const int row=4;

//污水列

const int col=4;

//污水面积

const int ALL=row*col;

int countALL=0;

//需要多少天

int coutDay=0;

int** A=(int**)malloc(sizeof(int*)*row);

void printfA(int **A)

{

for(int i=0;i<row;i++)

{

for(int j=0;j<col;j++)

{

printf("%d",A[i][j]);

}

printf("\n");

}

}

//初始化一个二维数组全为0

void initA(int **A)

{

for(int i=0;i<row;i++)

{

A[i]=(int*)malloc(sizeof(int)*col);

for(int j=0;j<col;j++)

{

A[i][j]=0;

}

}

}

//拷贝一个二维数组

void copy(int **A,int**B)

{

for(int i=0;i<row;i++)

{

for(int j=0;j<col;j++)

{

A[i][j]=B[i][j];

}

}

}

//是否全部污染了

bool isALLSuit(int**A)

{

for(int i=0;i<row;i++)

{

for(int j=0;j<col;j++)

{

if(A[i][j]!=1)

{

return false;

}

}

}

return true;

}

//污染

void setValue(int** today,int **tommorow)

{

for(int i=0;i<row;i++)

{

for(int j=0;j<col;j++)

{

if(today[i][j]==1)

{

//上

if(i-1>0)

{

tommorow[i-1][j]=1;

}

//右

if(j-1>0)

{

tommorow[i][j-1]=1;

}

//左

if(i+1<row)

{

tommorow[i+1][j]=1;

}

//下

if(j+1<col)

{

tommorow[i][j+1]=1;

}

}

}

}

}

int calculate(int** A)

{

countALL=0;

for(int i=0;i<row;i++)

{

for(int j=0;j<col;j++)

{

if(A[i][j]==0)

{

countALL++;

}

}

}

if(countALL==ALL)

{

return -1;

}

if(isALLSuit(A))

{

return coutDay;

}

else

{

//set value

int** tommorow=(int**)malloc(sizeof(int*)*row);

initA(tommorow);

copy(tommorow,A);

printfA(tommorow);

setValue(A,tommorow);

coutDay++;

return calculate(tommorow);

}

}

int main()

{

initA(A);

//设置污染源

A[0][0]=1;

return calculate(A);

}