## Sunday, December 27, 2015

### Coast Length - P1

http://jobs.p1.com/tech/costal.html
The island municipality of Soteholm is required to write a plan of action for their work with emission of greenhouse gases. They realize that a natural first step is to decide whether they are for or against global warming. For this purpose they have read the IPCC report on climate change and found out that the largest effect on their municipality could be the rising sea level.
The residents of Soteholm value their coast highly and therefore want to maximize its total length. For them to be able to make an informed decision on their position in the issue of global warming, you have to help them find out whether their coastal line will shrink or expand if the sea level rises. From height maps they have figured out what parts of their islands will be covered by water, under the different scenarios described in the IPCC report, but they need your help to calculate the length of the coastal lines.

You will be given a map of Soteholm as an N×M grid. Each square in the grid has a side length of 1 km and is either water or land. Your goal is to compute the total length of sea coast of all islands. Sea coast is all borders between land and sea, and sea is any water connected to an edge of the map only through water. Two squares are connected if they share an edge. You may assume that the map is surrounded by sea. Lakes and islands in lakes are not contributing to the sea coast.

Figure 1:
Gray squares are land and white squares are water. The thick black line is the sea coast. This example corresponds to Sample Input 1.

Input

The first line of the input contains two space separated integers N and M where 1 ≤ N, M ≤ 1000. The following N lines each contain a string of length M consisting of only zeros and ones. Zero means water and one means land.

Output

Output one line with one integer, the total length of the coast in km.

 Sample Input 1 Sample Output 1 5 6011110010110111000000010000000 20

1 以地图的四周，即地图的边沿，如下图黄色部分:

2 第1步解决了标识和区分内湖的问题，然后就解决数海岸线的问题了，我们分开两步来数，第一步数最外边的海岸线，第二部数格子之间的海岸线；

```const int MAX_N = 1001;
char arr[MAX_N][MAX_N];
int n, m;
const char WATER = '2';

inline bool isLegal(int r, int c)
{
return 0<=r && 0<=c && r<n && c<m;
}

void fillWater(int r, int c)
{
if (!isLegal(r, c)) return ;
if (arr[r][c] != '0') return ;

arr[r][c] = WATER;
fillWater(r-1, c);
fillWater(r+1, c);
fillWater(r, c-1);
fillWater(r, c+1);
}

int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d %d", &n, &m);
getchar();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
char a = getchar();
while (a != '0' && a != '1')
{
a = getchar();
}///< handle io crazy problems.
arr[i][j] = a;
}
}
for (int i = 0; i < n; i++)
{
fillWater(i, 0);
fillWater(i, m-1);
}
for (int j = 1; j+1 < m; j++)
{
fillWater(0, j);
fillWater(n-1, j);
}

int outEdge = 0, inEdge2 = 0;

for (int i = 0; i < n; i++)
{
if (arr[i][0] != WATER) outEdge++;
if (arr[i][m-1] != WATER) outEdge++;
}
for (int j = 0; j < m; j++)
{
if (arr[0][j] != WATER) outEdge++;
if (arr[n-1][j] != WATER) outEdge++;
}

for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (arr[i][j] == WATER)
{
if (isLegal(i-1, j))
{
if (arr[i-1][j] != WATER) inEdge2++;
}
if (isLegal(i+1, j))
{
if (arr[i+1][j] != WATER) inEdge2++;
}
if (isLegal(i, j-1))
{
if (arr[i][j-1] != WATER) inEdge2++;
}
if (isLegal(i, j+1))
{
if (arr[i][j+1] != WATER) inEdge2++;
}
}
else if (arr[i][j] != WATER)
{
if (isLegal(i-1, j))
{
if (arr[i-1][j] == WATER) inEdge2++;
}
if (isLegal(i+1, j))
{
if (arr[i+1][j] == WATER) inEdge2++;
}
if (isLegal(i, j-1))
{
if (arr[i][j-1] == WATER) inEdge2++;
}
if (isLegal(i, j+1))
{
if (arr[i][j+1] == WATER) inEdge2++;
}
}
}
}
printf("%d", outEdge + (inEdge2>>1));
return 0;
}```