題目
https://gmoj.net/senior/#main/show/6841
題解
這道題目我考場上搞了好久都沒有想清楚，考完后發現解法有很多，
解法1
—— S L S SLS SLS大佬的解法，
考慮通過植樹造林把森林變成一個矩形，
那么什么樣的點上面要種樹呢？
- 正上方、正下方都有
X的點； - 在一個’L’中的點（圖中的兩個位置Y中任意一個是X就要在A上面種樹）：
植樹造林之后我們就得到了一個凸多邊形，
怎么求答案呢？先把沿著它走的路徑上的點求出來，如下圖的+：
然后從一個到起點的距離大于到起點的切比雪夫距離的點開始，順時針或逆時針給+標號（因為這里寫不下兩位數，就用了26進制表示）：
然后把到起點的距離等于到起點的切比雪夫距離的點取出來，最短路徑為起點->它們中標號最大的點->多邊形的背后->它們中標號最小的點->起點，
實作比較麻煩，
解法2
—— x i a o q i xiaoqi xiaoqi大佬的解法
選樹林邊上y最小的點（這個點是必須經過的），然后把它左邊的點全部刪掉，再在它上面打上標記（不能走），接著從起點走到它的兩邊，再合并答案，
解法3
——大佬2016吳家慶的解法
其實和解法2類似，
找出樹林中y最小的點，從它向左修建一排柵欄（就是不能走的標記）：
接著對于每一個柵欄上的點，將它上、下到起點的距離合并即可，
注意當起點剛好在y最小的點向左的柵欄上時，答案是錯的，這時選擇y最大的點向右修柵欄即可，
解法4
——大佬LZA的解法
做凸包，
CODE（解法3）
#include<cstdio>
#include<cstring>
using namespace std;
#define M 4000005
#define N 2005
const int dx[8]={1,1,1,0,0,-1,-1,-1},dy[8]={0,1,-1,1,-1,0,1,-1};
char a[N][N];int f[N][N],data[M][2],n,m;
inline void bfs(int stx,int sty)
{
int x,y,xx,yy,head=0,tail=1;
data[1][0]=stx,data[1][1]=sty;
memset(f,0x3f,sizeof f);
f[stx][sty]=0;
while(head<tail)
{
x=data[++head][0],y=data[head][1];
for(int i=0;i<8;++i)
{
xx=x+dx[i],yy=y+dy[i];
if(xx&&yy&&xx<=n&&yy<=m&&a[xx][yy]=='.'&&f[xx][yy]>f[x][y]+1)
{
f[xx][yy]=f[x][y]+1;
data[++tail][0]=xx,data[tail][1]=yy;
}
}
}
}
int main()
{
freopen("forest.in","r",stdin);
freopen("forest.out","w",stdout);
int stx,sty,x=0,y=0,ans=999999999,up,down;
scanf("%d%d",&n,&m);
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]=='*'){stx=i,sty=j;goto out;}
out:
for(int j=1;j<=m;++j)
for(int i=1;i<=n;++i)
if(a[i][j]=='X'){x=i,y=j;goto judge;}
judge:
if(stx==x&&sty<y)
{
for(int j=1;j<=m;++j)
for(int i=1;i<=n;++i)
if(a[i][j]=='X'){x=i,y=j;goto mark;}
mark:
for(int i=y+1;i<=m;++i) a[x][i]='+';
}
else for(int i=1;i<y;++i) a[x][i]='+';
bfs(stx,sty);
for(int i=1;i<=m;++i) if(a[x][i]=='+')
{
up=f[x-1][i];
if(i>1&&f[x-1][i-1]<up) up=f[x-1][i-1];
if(i<m&&f[x-1][i+1]<up) up=f[x-1][i+1];
down=f[x+1][i];
if(i>1&&f[x+1][i-1]<down) down=f[x+1][i-1];
if(i<m&&f[x+1][i+1]<down) down=f[x+1][i+1];
if(up+down+2<ans) ans=up+down+2;
}
printf("%d\n",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/204673.html
標籤：其他
上一篇：C++特征碼查找 附加案例
下一篇：SDL嵌入qt視窗繪制圖片