题意:
在棋盘上摆两个兵,按照棋盘指示走,两个兵只有在‘#‘格才能位于同一格,问怎样摆放使得两个兵走的步数之和最大。
思路:
找出最长的一条路(长度为best),如果有两条不相同的,则为2*best ,若两条路有交集,则为 2*best-1 (一前一后放),由于路径固定,可将一条路径标记,看其他的是否与其有不为‘#’的交集就够了。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <map> #include <stack> #include <vector> #include <set> #include <queue> #pragma comment (linker,"/STACK:102400000,102400000") #define maxn 2005 #define MAXN 400005 #define mod 1000000000 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; int n,m,k,ans,cnt,tot,flag; char mp[maxn][maxn]; bool vis[maxn][maxn]; int dp[maxn][maxn]; int nx[maxn*maxn],ny[maxn*maxn]; int dfs(int x,int y) { if(dp[x][y]!=-1) return dp[x][y]; int i,j,t,best=0; if(mp[x][y]==‘^‘) { if(vis[x-1][y]) return INF; vis[x-1][y]=1; t=dfs(x-1,y); vis[x-1][y]=0; } else if(mp[x][y]==‘v‘) { if(vis[x+1][y]) return INF; vis[x+1][y]=1; t=dfs(x+1,y); vis[x+1][y]=0; } else if(mp[x][y]==‘<‘) { if(vis[x][y-1]) return INF; vis[x][y-1]=1; t=dfs(x,y-1); vis[x][y-1]=0; } else if(mp[x][y]==‘>‘) { if(vis[x][y+1]) return INF; vis[x][y+1]=1; t=dfs(x,y+1); vis[x][y+1]=0; } else t=-1; dp[x][y]=t+1; return t+1; } void dfs1(int x,int y) { // printf("x:%d y:%d\n",x,y); if(mp[x][y]==‘#‘) { if(k) flag=1; return ; } vis[x][y]=1; if(mp[x][y]==‘^‘) { if(!vis[x-1][y]) dfs1(x-1,y); } else if(mp[x][y]==‘v‘) { if(!vis[x+1][y]) dfs1(x+1,y); } else if(mp[x][y]==‘<‘) { if(!vis[x][y-1]) dfs1(x,y-1); } else if(mp[x][y]==‘>‘) { if(!vis[x][y+1]) dfs1(x,y+1); } } void solve() { int i,j,t,best=-1; cnt=0; memset(dp,-1,sizeof(dp)); memset(vis,0,sizeof(vis)); for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { if(mp[i][j]!=‘#‘) { vis[i][j]=1; t=dfs(i,j); vis[i][j]=0; if(t>best) { best=t; cnt=1; nx[1]=i,ny[1]=j; } else if(t==best) { cnt++; nx[cnt]=i,ny[cnt]=j; } if(best>=INF) { ans=-1; return ; } } } } if(best==-1) { ans=0; return ; } memset(vis,0,sizeof(vis)); k=0; dfs1(nx[1],ny[1]); flag=0; k=1; for(i=2;i<=cnt;i++) { dfs1(nx[i],ny[i]); if(flag) break ; } ans=2*best-1+flag; } int main() { int i,j,t; while(~scanf("%d%d",&n,&m)) { for(i=1; i<=n; i++) { scanf("%s",mp[i]+1); } solve(); printf("%d\n",ans); } return 0; }