題意：從任意一個(gè)任意一個(gè)可走的點(diǎn)開始找一個(gè)最長(zhǎng)的路，這條路如果有轉(zhuǎn)彎的話，
那么必須是 90度，或者沒有轉(zhuǎn)彎！

思路： 首先用dfs將所有可走點(diǎn)開始的 8 個(gè)方向上的線段的最長(zhǎng)長(zhǎng)度求出來 ！
step[i][j][k] 表示的是（i,j）沿著k方向一直走到頭或者轉(zhuǎn)彎時(shí)的最長(zhǎng)步數(shù)！
最后枚舉每一個(gè)可走點(diǎn)轉(zhuǎn)彎為90度的路徑，找到最長(zhǎng)的長(zhǎng)度！
step[i][j][k1] + step[i][j][k2] 就是 (i, j)這個(gè)點(diǎn) k1 和 k2方向構(gòu)成90度！

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define N 105 6 using namespace std; 7 8 int step[N][N][8]; 9 int dir[8][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1} }; 10 int index[8][2] = { {0, 1}, {1, 3}, {2, 3}, {0, 2}, {5, 6}, {5, 7}, {4, 7}, {4, 6}};//每一個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的轉(zhuǎn)彎的枚舉 11 char mp[N][N], vis[N][N]; 12 int n; 13 14 bool judge(int x, int y){ 15 if(x < 1 || y < 1 || x > n || y > n) 16 return false; 17 if( mp[x][y] == '#') return false; 18 19 return true; 20 } 21 22 void dfs(int x, int y){ 23 for(int i = 0; i < 8; ++i){ 24 int xx = x + dir[i][1]; 25 int yy = y + dir[i][0]; 26 if(!judge(xx, yy)) 27 step[x][y][i] = 1; 28 else{ 29 if( !step[xx][yy][i] )//記憶話的趕腳 30 dfs(xx, yy); 31 step[x][y][i] = 1 + step[xx][yy][i]; 32 } 33 } 34 } 35 36 int main(){ 37 while(scanf("%d", &n) && n){ 38 memset(step, 0, sizeof(step)); 39 memset(vis, 0, sizeof(vis)); 40 for(int i = 1; i <= n; ++i) 41 scanf("%s", mp[i]+1); 42 43 for(int i = 1; i <= n; ++i) 44 for(int j = 1; j <= n; ++j) 45 if(mp[i][j] == '.') 46 dfs(i, j); 47 48 int maxN = -1; 49 for(int i=1; i <= n; ++i) 50 for(int j = 1; j <= n; ++j){ 51 if(mp[i][j] == '.') 52 for(int k = 0; k < 8; ++k) 53 maxN = max(maxN, step[i][j][index[k][0]] + step[i][j][index[k][1]] ); 54 } 55 printf("%d\n", maxN - 1);//因?yàn)槎嗉恿艘淮喂拯c(diǎn)！ 56 } 57 return 0; 58 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/hujunzheng/p/3993741.html

總結(jié)

以上是生活随笔為你收集整理的2014 网选 5024 Wang Xifeng's Little Plot的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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