題意：
在可以行走的區(qū)域內(nèi)，只能轉(zhuǎn)一次90度的彎，問你最長這條路可以多長。
思路：
我們可以看到

/* 123 8 4 765 */

轉(zhuǎn)90度的路徑會是橫豎，也就是1-3-5-7;
還有斜的：2-4-6-8；
我們可以對一個點直接BFS/暴力一下，方向是八個方向，然后計算對應(yīng)的90度方向上的距離和，開個數(shù)組表示某方向上的路徑長度，我們可以發(fā)現(xiàn)90度方向在數(shù)組上的規(guī)律，然后再暴力找個最大。
復(fù)雜度也不高。
貼一發(fā)挫code…….

//#include<bits/stdc++.h> #include<cstdio> #include<iostream> #include<math.h> #include<string.h> #include<algorithm> using namespace std; typedef long long LL; typedef unsigned long long ULL; const double eps=1e-5; const double pi=acos(-1.0); const int mod=1e8+7; const LL INF=0x3f3f3f3f;const int N=1e2+7; char ma[N][N]; int n;int dx[8]={-1,-1,-1,0,1,1,1,0}; int dy[8]={-1,0,1,1,1,0,-1,-1};int Judge(int x,int y) {if(x<0||y<0||x>=n||y>=n||ma[x][y]=='#')return 0;return 1; }int bfs(int i,int j) {int sum[8];for(int k=0;k<8;k++)sum[k]=1;for(int k=0;k<8;k++){int aa=i+dx[k];int bb=j+dy[k];while(Judge(aa,bb)){sum[k]++;aa+=dx[k];bb+=dy[k];}}int ans=0; // for(int k1=0;k1<8;k1+=2) // for(int k2=1;k2<8;k2+=2) // ans=max(ans,sum[k1]+sum[k2]);for(int k1=0;k1<8;++k1)for(int k2=0;k2<8;++k2)if((k1%2==k2%2)&&k1!=k2) //對于數(shù)組的特性，奇數(shù)都是斜方向，偶數(shù)都是豎直方向。 ans=max(ans,sum[k1]+sum[k2]);return ans-1; }int main() {while(~scanf("%d",&n)){if(!n) break;int i,j,ans;for(i=0;i<n;i++)scanf("%s",ma[i]);ans=0;for(i=0;i<n;i++)for(j=0;j<n;j++)if(ma[i][j]=='.')ans=max(ans,bfs(i,j));printf("%d\n",ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/keyboarder-zsq/p/5934891.html

總結(jié)

以上是生活随笔為你收集整理的hdoj5024【BFS/暴力】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。