http://acm.hdu.edu.cn/showproblem.php?pid=3368
题意:模拟黑白棋,下一步黑手最大可以转化多少个白旗
分析:暴力
原先的思路是找到D然后遍历其八个方向,直到结尾为*的时候计算该个数,这种思路的错误点在于,于下组数据
********
********
**D*D*D*
***LLL**
**DL*LD*
***LLL**
**D*D*D*
********
这个答案是8,若按照我的思路答案是1
正解:遍历*,加上它八个方向的所有L长度
#include<stdio.h>
#include<string.h>
const int MN=10;
char mat[MN][MN];
int row[]= {1,-1,0,0,-1,-1,1,1};
int col[]= {0,0,1,-1,-1,1,-1,1};
int cnt;
void DFS(int x,int y,int k)
{
int xx=x+row[k];
int yy=y+col[k];
if(xx>=0 && xx<8 && yy>=0 && yy<8 && mat[xx][yy]=='L')
{
cnt++;
DFS(xx,yy,k);
}
else if(mat[xx][yy]!='D') cnt=0;
}
int main()
{
int i,j,T,k;
int cas=1;
scanf("%d",&T);
while(T--)
{
for(i=0; i<8; i++)
scanf("%s",mat[i]);
int ans=0;
for(i=0; i<8; i++)
for(j=0; j<8; j++)
{
if(mat[i][j]=='*')
{
int tmp=0;
for(k=0; k<8; k++)
{
cnt=0;
DFS(i,j,k);
tmp+=cnt;
}
if(ans<tmp) ans=tmp;
}
}
printf("Case %d: %d\n",cas++,ans);
}
return 0;
}