时间紧张，先记一笔，后续优化与完善。
这个是2010杭州区域赛的目题。
bfs出最短路，二分谜底，dp判断可行性。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=17,maxm=300;
int n,m,lon,ret;
char a[maxn][maxn];
int b[maxn],d[maxn][maxn];
int quex[maxm],quey[maxm],text[maxn][maxn],f[maxn][maxn];
int dp[1<<17][20];
int work(int ans)
{
memset(dp,1,sizeof(dp));
for(int i=0;i<lon;i++)
if(d[16][i+1]<=ans)
{
dp[1<<i][i+1]=d[16][i+1];
if(b[i+1]==1)
dp[1<<i][i+1]=0;
}
for(int k=0;k<(1<<lon);k++)
for(int i=0;i<lon;i++)
for(int j=0;j<lon;j++)
if(dp[k][i+1]+d[i+1][j+1]<=ans)
{
dp[k|(1<<j)][j+1]=min(dp[k|(1<<j)][j+1],dp[k][i+1]+d[i+1][j+1]);
if(b[j+1]==1)
if((k&(1<<j))==0)
dp[k|(1<<j)][j+1]=0;
}
for(int k=0;k<(1<<lon);k++)
if((k&((1<<ret)-1))==(1<<ret)-1)
for(int i=1;i<=lon;i++)
if(dp[k][i]<=ans)
return(1);
return(0);
}
void bfs(int t,int s)
{
memset(text,0,sizeof(text));
memset(f,1,sizeof(f));
f[t][s]=0;
text[t][s]=1;
int front=1,end=0;
quex[++end]=t;
quey[end]=s;
int u=a[t][s];
d[u][u]=0;
while(front<=end)
{
int x=quex[front],y=quey[front++];
if(a[x][y]=='D') continue;
int v=a[x][y];
if(v>=1&&v<=16)
{
d[u][v]=f[x][y];
d[v][u]=f[x][y];
}
if(x>1)
{
if(f[x-1][y]>f[x][y]+1)
{
f[x-1][y]=f[x][y]+1;
if(!text[x-1][y])
{
quex[++end]=x-1;
quey[end]=y;
}
}
}
if(x<n)
{
if(f[x+1][y]>f[x][y]+1)
{
f[x+1][y]=f[x][y]+1;
if(!text[x+1][y])
{
quex[++end]=x+1;
quey[end]=y;
}
}
}
if(y>1)
{
if(f[x][y-1]>f[x][y]+1)
{
f[x][y-1]=f[x][y]+1;
if(!text[x][y-1])
{
quex[++end]=x;
quey[end]=y-1;
}
}
}
if(y<m)
{
if(f[x][y+1]>f[x][y]+1)
{
f[x][y+1]=f[x][y]+1;
if(!text[x][y+1])
{
quex[++end]=x;
quey[end]=y+1;
}
}
}
}
}
int main()
{
// freopen("in.txt","r",stdin);
while(scanf("%d %d",&n,&m),n||m)
{
lon=0;
for(int i=1;i<=n;i++)
scanf("%s",&a[i][1]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]=='Y')
{
a[i][j]=++lon;
b[lon]=2;
}
else if(a[i][j]=='F')
{
a[i][j]=16;
}
ret=lon;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]=='G')
{
a[i][j]=++lon;
b[lon]=1;
}
memset(d,1,sizeof(d));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]>=1&&a[i][j]<=16)
bfs(i,j);
int ture=0;
for(int i=1;i<=ret;i++)
if(d[16][i]>300)
ture=1;
if(ret==0)
{
printf("0\n");
continue;
}
if(ture)
{
printf("-1\n");
continue;
}
int st=0,ed=1000,mid;
while(st<ed)
{
int mid=(st+ed)>>1;
if(work(mid))
ed=mid;
else
st=mid+1;
}
printf("%d\n",st);
}
return 0;
}
文章结束给大家分享下程序员的一些笑话语录：
自行车
一个程序员骑着一个很漂亮的自行车到了公司，另一个程序员看到了他，问 到，“你是从哪搞到的这么漂亮的车的？”
骑车的那个程序员说， “我刚从那边过来， 有一个漂亮的姑娘骑着这个车过来， 并停在我跟前，把衣服全脱了，然后对我说，‘你想要什么都可以’”。
另一个程序员马上说到， “你绝对做了一个正确的选择， 因为那姑娘的衣服你 并不一定穿得了”。