网易补招第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;
}
查看10道真题和解析