这个题需要注意细节,不然卡在那儿很烦,我的做法比较无脑,代码太长,但理解方便一点。
#include<cstdio>
#include<cstring>
char grid[1005][1005];
int m,n;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};//分别表示上下左右四个方向
//为1表示这个方向有接口,为0表示这个方向没有接口
/*int type[11][4]={{1,1,0,0},{0,1,1,0},
{1,0,0,1},{0,0,1,1},
{0,1,0,1},{1,0,1,0},
{1,1,1,0},{1,1,0,1},
{1,0,1,1},{0,1,1,1},
{1,1,1,1}};
这里面可以简化下面的自己赋值,但还不会用*/
int dfs(int x,int y)
{
if(grid[x][y]=='*')
grid[x][y]='!';
else
return 0;
for(int i=0;i<4;i++)
{
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(xx>=0&&xx<3*m&&yy>=0&&yy<3*n) //注意范围
dfs(xx,yy);
}
return 1;
}
int main()
{
while(scanf("%d%d",&m,&n)==2&&m!=-1&&n!=-1)
{
memset(grid,0,sizeof(grid));
int cunt=0;
char cnt;
for(int i=0;i<m;i++)
{
getchar();
for(int j=0;j<n;j++)
{
scanf("%c",&cnt);
if(cnt=='A')
{
grid[i*3][j*3+1]='*';
grid[i*3+1][j*3+1]='*';
grid[i*3+1][j*3]='*';
}
if(cnt=='B')
{
grid[i*3][j*3+1]='*';
grid[i*3+1][j*3+1]='*';
grid[i*3+1][j*3+2]='*';
}
if(cnt=='C')
{
grid[i*3+2][j*3+1]='*';
grid[i*3+1][j*3+1]='*';
grid[i*3+1][j*3]='*';
}
if(cnt=='D')
{
grid[i*3+2][j*3+1]='*';
grid[i*3+1][j*3+1]='*';
grid[i*3+1][j*3+2]='*';
}
if(cnt=='E')
{
grid[i*3][j*3+1]='*';
grid[i*3+1][j*3+1]='*';
grid[i*3+2][j*3+1]='*';
}
if(cnt=='F')
{
grid[i*3+1][j*3]='*';
grid[i*3+1][j*3+1]='*';
grid[i*3+1][j*3+2]='*';
}
if(cnt=='G')
{
grid[i*3+1][j*3]='*';
grid[i*3+1][j*3+1]='*';
grid[i*3+1][j*3+2]='*';
grid[i*3][j*3+1]='*';
}
if(cnt=='H')
{
grid[i*3+2][j*3+1]='*';
grid[i*3+1][j*3+1]='*';
grid[i*3][j*3+1]='*';
grid[i*3+1][j*3]='*';
}
if(cnt=='I')
{
grid[i*3+1][j*3]='*';
grid[i*3+1][j*3+1]='*';
grid[i*3+1][j*3+2]='*';
grid[i*3+2][j*3+1]='*';
}
if(cnt=='J')
{
grid[i*3][j*3+1]='*';
grid[i*3+1][j*3+1]='*';
grid[i*3+1][j*3+2]='*';
grid[i*3+2][j*3+1]='*';
}
if(cnt=='K')
{
grid[i*3][j*3+1]='*';
grid[i*3+1][j*3]='*';
grid[i*3+1][j*3+1]='*';
grid[i*3+1][j*3+2]='*';
grid[i*3+2][j*3+1]='*';
}
}
}
for(int i=0;i<m*3;i++) //注意循环的范围
for(int j=0;j<n*3;j++)
if(dfs(i,j)) //先进入DFS算法再判断是否可行
++cunt;
printf("%d\n",cunt);
}
return 0;
}
网友评论