网易补招第1题解法

给定矩阵找出里面NETS的个数。

1. 每个字符在矩阵里必须是一个连通分量，每个元素与周围的八个元素相连。

2. 矩阵里'.'表示空白，'#'表示笔画。（之前写成‘*’表示笔画，实际上是'#'）

3. 每个字符可能旋转90度，180度，270度。

下面是我的解法：

1. 给定元素坐标，若当前元素之前没有遍历过，则找出包含当前元素的连通分量。

2. 判断连通分量中元素的个数，然后再判断连通分量是否是4个字符中的一个。

3. 解法能保证判断连通分量是哪个字符的时候，传入的是这个字符最靠上然后最靠左的点的坐标。

#include <stdio.h>
#include <stdlib.h>

int nrow, ncol;
char matrix[500][501]; # 用来表示输入矩阵
int step[8][2] = {     # 用来遍历元素周围的八个元素                   
    {-1, 0}, {-1, 1}, {0, 1}, {1, 1},
    {1, 0}, {1, -1}, {0, -1}, {-1, -1}
}; 

int cc(int i, int j)
{
    // 计算包含元素i,j的连通分量包含的元素个数
    int tmp, nr, nc, ret=1;
    if(matrix[i][j] != '#')
        return 0;
    matrix[i][j] = '*'; // 代表当前元素已遍历，'*'号用来判断连通分量代表的字符
    for(tmp=0; tmp<8; tmp++)
    {
        nr = i+step[tmp][0];
        nc = j+step[tmp][1];
        if(nr>=0 && nr<nrow && nc>=0 && nc<ncol)
            ret += cc(nr, nc);
    }
    return ret;
}

int check_down(int i, int j)
{
    // 从i，j开始，向下遍历有多少个连续的'*'
    int ret = 0;
    if(i<0 || j<0 || i>=nrow || j>= ncol)
        return 0;
    else
        while(i<nrow && matrix[i][j] == '*')
        {
            ret += 1;
            i +=1;
        }
    return ret;
}

int check_right(int i, int j)
{  // 从i，j开始，向右遍历有多少个连续的'*'   
    int ret = 0;
    if(i<0 || j<0 || i>=nrow || j>= ncol)
        return 0;
    else
        while(j<ncol && matrix[i][j] == '*')
        {
            ret += 1;
            j +=1;
        }
    return ret;
}

int check_diag(int i, int j)
{
    // 从i，j开始向右下遍历，有多少个连续的'*'，用在判断N里
    int ret = 0;
    if(i<0 || j<0 || i>=nrow || j>= ncol)
        return 0;
    else
        while(i<nrow && j<ncol && matrix[i][j] == '*')
        {
            ret += 1;
            i +=1;
            j +=1;
        }
    return ret;
}

int check_rdiag(int i, int j)
{
    // 从i，j开始向左下遍历，有多少个连续的'*'，用在判断N里
    int ret = 0;
    if(i<0 || j<0 || i>=nrow || j>= ncol)
        return 0;
    else
        while(i<nrow && j>=0 && matrix[i][j] == '*')
        {
            ret += 1;
            i +=1;
            j -=1;
        }
    return ret;
}

int check_T(int i, int j)
{
    // 判断连通分量是不是T
    int right=check_right(i, j), down=0;
    if(right==1)
    {
        down = check_down(i, j);
        if(down==7)
        {
            if (check_right(i+3, j)==5) // T顺时针转了270度
                return 1;
            if(check_right(i+3, j-4)==5) // T顺时针转了90度
                return 1;
            return 0;
        }
        else if(down==5)
        {
            return (check_right(i+4, j-3) == 7); // T顺时针转了180度
        }
        else
            return 0;
    }
    else if(right == 7)
    {
        return (check_down(i, j+3)==5); // T没有转动
    }
    else
        return 0;
}

int check_E(int i, int j)
{
    // 判断是不是E
    int right = check_right(i, j), down;
    if(right==7)
    {
        down = check_down(i, j);
        if(down==1)
        {
            // E 顺时针转了180度
            if(check_right(i+2, j)!=7)
                return 0;
            if(check_right(i+4, j)!=7)
                return 0;
            if(check_down(i, j+6)!=5)
                return 0;
            return 1;
        }
        else if(down==5)
        {
            // E 没有转动
            if(check_right(i+2, j)!=7)
                return 0;
            if(check_right(i+4, j)!=7)
                return 0;
            return 1;
        }
        else
            return 0;
    }
    else if(right==5)
    {
        // E 顺时针转了90度
        if(check_down(i, j)!=7)
            return 0;
        if(check_down(i, j+2)!=7)
            return 0;
        if(check_down(i, j+4)!=7)
            return 0;
        return 1;
    }
    else if(right==1)
    {
        // E 转了270度
        if(check_down(i, j)!=7)
            return 0;
        if(check_down(i, j+2)!=7)
            return 0;
        if(check_down(i, j+4)!=7)
            return 0;
        if(check_right(i+6, j)!=5)
            return 0;
        return 1;
    }
    else
        return 0;
}

int check_S(int i, int j)
{
    // 判断是不是S
    int right = check_right(i, j);
    if(right==7)
    {
        // S 没转，或者转了180度，两个图案一样
        if(check_down(i, j)!=3)
            return 0;
        if(check_right(i+2, j)!=7)
            return 0;
        if(check_down(i+2, j+6)!=3)
            return 0;
        if(check_right(i+4, j)!=7)
            return 0;
        return 1;
    }
    else if(right==1)
    {
        // S转了90度或者270度
        if(check_down(i, j)!=7)
            return 0;
        if(check_right(i+6, j)!=3)
            return 0;
        if(check_down(i, j+2)!=7)
            return 0;
        if(check_right(i, j+2)!=3)
            return 0;
        if(check_down(i, j+4)!=7)
            return 0;
        return 1;
    }
    else
        return 0;
}


int check_N(int i, int j)
{
    // 判断是不是N
    int right=0, tmp;
    for(tmp=j; tmp<ncol && matrix[i][tmp] == '*'; tmp++)
        right +=1;
    if(right==2)
    {
        // N 没转或者转了180度
        if(check_down(i, j) != 5)
            return 0;
        if(check_diag(i, j+1) != 5)
            return 0;
        if(check_down(i, j+6) != 5)
            return 0;
        return 1;
    }
    else if(right==5)
    {
        // N 转了90度或者270度。
        if(check_rdiag(i+1, j+4)!=5)
            return 0;
        if(check_right(i+6, j)!=5)
            return 0;
        return 1;
    }
    else
        return 0;
}

int main()
{
    int i, j, ret, N=0, T=0, E=0, S=0;
    scanf("%d %d", &nrow, &ncol);

    for(i=0; i<nrow; i++)
        scanf("%s", matrix[i]);
    for(i=0; i<nrow; i++)
        for(j=0; j<ncol; j++)
        {
            //printf("%d %d\n", i, j);
            ret = cc(i, j);
            if(ret==15)
            {
                // check if N
                N += check_N(i, j);
            }
            else if(ret == 11)
            {
                // check T
                T += check_T(i, j);
            }
            else if(ret == 23)
            {
                E += check_E(i, j);
                S += check_S(i, j);
            }
        }
    printf("N: %d\nT: %d\nE: %d\nS: %d\n", N, T, E, S);
    return 0;
}