codefoces-B. Plus from Picture
题目链接
You have a given picture with size w×h. Determine if the given picture has a single “+” shape or not. A “+” shape is described below:
A “+” shape has one center nonempty cell.
There should be some (at least one) consecutive non-empty cells in each direction (left, right, up, down) from the center. In other words, there should be a ray in each direction.
All other cells are empty.
Find out if the given picture has single “+” shape.
Input
The first line contains two integers h and w (1≤h, w≤500) — the height and width of the picture.
The i-th of the next h lines contains string si of length w consisting “.” and “" where “.” denotes the empty space and "” denotes the non-empty space.
Output
If the given picture satisfies all conditions, print “YES”. Otherwise, print “NO”.
You can output each letter in any case (upper or lower).
Examples
input
5 6
......
..*...
.****.
..*...
..*...
output
YES
input
3 5
..*..
****.
.*...
output
NO
input
7 7
.......
...*...
..****.
...*...
...*...
.......
.*.....
output
NO
input
5 6
..**..
..**..
******
..**..
..**..
output
NO
input
3 7
.*...*.
***.***
.*...*.
output
NO
input
5 10
..........
..*.......
.*.******.
..*.......
..........
outputCopy
NO
Note
In the first example, the given picture contains one “+”.
In the second example, two vertical branches are located in a different column.
In the third example, there is a dot outside of the shape.
In the fourth example, the width of the two vertical branches is 2.
In the fifth example, there are two shapes.
In the sixth example, there is an empty space inside of the shape.
题意：
给你一个图由*和.组成，让你判断这个图中的*是否组成+这个标记；这个不是标准的+，“+”形状具有一个中心非空单元。
从中心开始，每个方向（左，右，上，下）应该有一些（至少一个）连续的非空单元。换句话说，每个方向都应该有一条光线。
解题思路：
刚开始时我想了一个错误的思路，每一个找到*就对它周围的找一遍，然后出项一次就认为成功，否则都失败；然后，再dfs找它们是一个连续的*；代码很快打出交了，然后wa在57组样例；
这一组
5 5
.....
..***
..*..
.***.
..*..
这个样例一看就发现了问题，不在一个十字线上但是同一个图也是YES，所以我觉得是之前看题考虑不够仔细；
然后，我觉得可以按题意直接分别对出现一个的一行和一列进行查找这样肯定可以保证在一个十字的范围内；
#include<bits/stdc++.h>
using namespace std;
const int maxn = 610;
char s[maxn][maxn];
int a[maxn][maxn];
int main()
{
int h,w;
cin>>h>>w;
for(int i=1; i<=h; i++
cin>>s[i]+1;
for(int i=1; i<=h; i++)
for(int j=1; j<=w; j++)//换成数字，这样比较好操作；
if(s[i][j]=='*')
a[i][j]=1;
int flag=1;//对行进行
for(int i=1; i<=h&&flag; i++)
for(int j=1; j<=w&&flag; j++)
if(a[i][j])//一旦出现，就对出现的这一行进行查找；
{
for(int k=i; k<=h; k++)
if(a[k][j])
a[k][j]=2;//标记查找过；
else
break;
flag=0;
}
flag=1;
int flag1=0;
for(int i=1; i<=h&&flag; i++)
for(int j=1; j<=w&&flag; j++)
if(a[i][j]==1)//没被查找过的*，继续查找；
{
for(int k=j; k<=w; k++)
{
if(a[i][k]==2&&a[i][k+1]==1&&a[i+1][k]==2)//为了找到十字标志；
flag1=1;
if(a[i][k])//每次都标记都查找过;
a[i][k]=2;
else break;
}
flag=0;
}
for(int i=1; i<=h; i++)
for(int j=1; j<=w; j++)
if(a[i][j]==1)//一旦还有另一个图必不可能;
flag1=0;
if(flag1)
cout<<"YES";
else
cout<<"NO";
return 0;
}
如果对我一开始的那个错误的代码感兴趣也可以看看；
#include<bits/stdc++.h>
using namespace std;
const int maxn = 610;
char s[maxn][maxn];
int a,b,res;
int vis[maxn][maxn];
int dis[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
int dfs(int x1,int y1)
{
vis[x1][y1]=1;//标记
s[x1][y1]='.';//初始化；
for(int k=0; k<=3; k++)//方向
{
int x,y;
x=x1+dis[k][0];
y=y1+dis[k][1];
if(x<1||x>a||y<1||y>b)
continue;
if(s[x][y]=='*'&&vis[x][y]==0)
{
res++;
vis[x][y]=1;//标记
//s[x][y]='.';
dfs(x,y);//递归
vis[x][y]=0;
}
}
return res;
}
int main()
{
cin>>a>>b;
memset(vis,0,sizeof(vis));
memset(s,0,sizeof(s));
for(int i=1; i<=a; i++)
{
for(int j=1; j<=b; j++)
{
cin>>s[i][j];
}
}
int ans=0,sum=0;
for(int i=1; i<=a; i++)
for(int j=1; j<=b; j++)
{
if(s[i][j]=='*')
if(s[i][j+1]=='*'&&s[i+1][j]=='*'&&s[i][j-1]=='*'&&s[i-1][j]=='*')
{
sum++;
}
}
for(int i=1; i<=a; i++)
{
for(int j=1; j<=b; j++)
{
if(s[i][j]=='*')
{
res=1;
dfs(i,j);
if(res>0)
{
ans++;
}
}
}
}
//cout<<"sum:"<<sum<<"ans:"<<ans<<endl;
if(sum==1&&ans==1)
{
cout<<"YES";
}
else
cout<<"NO";
return 0;
}
查看5道真题和解析