[cpp]
描述：對於這道題，實在想不出如何用動規，所以就直接bfs
#include <cstdio>
#include <cstring>
char s[5010][15];
int main()
{
// freopen("a.txt","r",stdin);
int n,flag;
while(scanf("%d",&n)!=EOF)
for(int i=0; i<n; i++)
{
scanf("%s",s[0]);
flag=12;
int last=1,first=0;
while(first<last)
{
int c=0;
for(int i=0; i<12; i++) if(s[first][i]=='o') c++;
if(c<flag) flag=c;
for(int i=0; i<12; i++)
{
if(i+2<12&&s[first][i]=='o'&&s[first][i+1]=='o'&&s[first][i+2]=='-')
{
strcpy(s[last],s[first]);
s[last][i]=s[last][i+1]='-';
s[last][i+2]='o';
last++;
}
if(i-2>=0&&s[first][i]=='o'&&s[first][i-1]=='o'&&s[first][i-2]=='-')
{
strcpy(s[last],s[first]);
s[last][i]=s[last][i-1]='-';
s[last][i-2]='o';
last++;
}
}
first++;
}
printf("%d\n",flag);
}
return 0;
}
描述：對於這道題，實在想不出如何用動規，所以就直接bfs
#include <cstdio>
#include <cstring>
char s[5010][15];
int main()
{
// freopen("a.txt","r",stdin);
int n,flag;
while(scanf("%d",&n)!=EOF)
for(int i=0; i<n; i++)
{
scanf("%s",s[0]);
flag=12;
int last=1,first=0;
while(first<last)
{
int c=0;
for(int i=0; i<12; i++) if(s[first][i]=='o') c++;
if(c<flag) flag=c;
for(int i=0; i<12; i++)
{
if(i+2<12&&s[first][i]=='o'&&s[first][i+1]=='o'&&s[first][i+2]=='-')
{
strcpy(s[last],s[first]);
s[last][i]=s[last][i+1]='-';
s[last][i+2]='o';
last++;
}
if(i-2>=0&&s[first][i]=='o'&&s[first][i-1]=='o'&&s[first][i-2]=='-')
{
strcpy(s[last],s[first]);
s[last][i]=s[last][i-1]='-';
s[last][i-2]='o';
last++;
}
}
first++;
}
printf("%d\n",flag);
}
return 0;
}
