2014 网选 5024 Wang Xifeng's Little Plot

题意:从任意一个任意一个可走的点开始找一个最长的路,这条路如果有转弯的话,
那么必须是 90度,或者没有转弯!

思路: 首先用dfs将所有可走点开始的 8 个方向上的线段的最长长度求出来 !
step[i][j][k] 表示的是(i,j)沿着k方向一直走到头或者转弯时的最长步数!
最后枚举每一个可走点转弯为90度的路径,找到最长的长度!
step[i][j][k1] + step[i][j][k2] 就是 (i, j)这个点 k1 和 k2方向构成90度!

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 105
using namespace std; int step[N][N][];
int dir[][] = { {, }, {, }, {-, }, {, -}, {-, -}, {, }, {-, }, {, -} };
int index[][] = { {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }};//每一个节点所对应的转弯的枚举
char mp[N][N], vis[N][N];
int n; bool judge(int x, int y){
if(x < || y < || x > n || y > n)
return false;
if( mp[x][y] == '#') return false; return true;
} void dfs(int x, int y){
for(int i = ; i < ; ++i){
int xx = x + dir[i][];
int yy = y + dir[i][];
if(!judge(xx, yy))
step[x][y][i] = ;
else{
if( !step[xx][yy][i] )//记忆话的赶脚
dfs(xx, yy);
step[x][y][i] = + step[xx][yy][i];
}
}
} int main(){
while(scanf("%d", &n) && n){
memset(step, , sizeof(step));
memset(vis, , sizeof(vis));
for(int i = ; i <= n; ++i)
scanf("%s", mp[i]+); for(int i = ; i <= n; ++i)
for(int j = ; j <= n; ++j)
if(mp[i][j] == '.')
dfs(i, j); int maxN = -;
for(int i=; i <= n; ++i)
for(int j = ; j <= n; ++j){
if(mp[i][j] == '.')
for(int k = ; k < ; ++k)
maxN = max(maxN, step[i][j][index[k][]] + step[i][j][index[k][]] );
}
printf("%d\n", maxN - );//因为多加了一次拐点!
}
return ;
}
上一篇:andriod RadioButton


下一篇:【代码笔记】iOS-竖状图