题意读了半年,英语太渣,题意是摆两个棋子在棋盘上作为起点,但是起点不能在#上,然后按照图的指示开始走, < 左 > 右 ^上 v下,走的时候只能按照图的指示走,如果前方是 #的话,可以走进去,但是 走进去之后便不能再走了,走的途中两个棋子不能相碰,但是最终都走到同一个#里是没事的,并且若是能走 无限步的话 输出 -1, 例如 > < 这样左右左右的走就能无限走,然后问你 两个棋子走的最大步数的和
一开始被输出-1给困住了,因为除了 .> <这样以外 还可以刚好形成一个圈,这样不太好判,而且不太敢写dfs因为 图是 2000 * 2000的有点大,反向的DFS也没想到,没法子也只能记忆化搜索一下,设dis[i][j]代表 由 (i,j)作为 起点能走的最远步数,这样觉得时间上应该能过去,然后枚举每一个点作为起点 进行深搜,这里就能判断是否为-1的情况,因为图为 2000 * 2000的,所以最多让你走 4000000步数,两个棋子一前一后跟着走的话 那么最多不会超过8000000,所以可以设置一个最大值MAXN = 8000000,一旦 重新走了标记过的也就是路过的点 就返回这个值,就能判定是否为-1,
求出每个点作为起点的最大步数以后,开始寻找,若有两个点的最大步数相同,而且他们在走的过程中没有相碰,这样最大步数和 就是 ans + ans ,若找不到的话 一前一后放置两个棋子肯定就是最优得了 也就是 ans + ans - 1,好了就是代码的 实现了,深搜写的有点搓,
const int MAXN = 8000000 + 55; char aa[2000 + 55][2000 + 55]; int mp[2000 + 55][2000 + 55]; int xx[5] = {-1,1,0,0}; int yy[5] = {0,0,-1,1}; int dis[2000 + 55][2000 + 55]; bool vis[2000 + 55][2000 + 55]; int bb[2000 + 55][2000 + 55]; int n,m; int ans; void init() { memset(aa,0,sizeof(aa)); memset(mp,0,sizeof(mp)); memset(dis,-1,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(bb,-1,sizeof(bb)); } bool input() { while(scanf("%d %d",&n,&m) == 2) { for(int i=0;i<n;i++) { scanf("%s",aa[i]); for(int j=0;j<m;j++) { if(aa[i][j] == '#')mp[i][j] = -1; if(aa[i][j] == '^')mp[i][j] = 0; if(aa[i][j] == 'v')mp[i][j] = 1; if(aa[i][j] == '<')mp[i][j] = 2; if(aa[i][j] == '>')mp[i][j] = 3; } } return false; } return true; } bool isok(int x,int y) { if(x <0 || x >=n || y < 0 || y >= m)return true; return false; } int dfs1(int x,int y) { if(isok(x,y))return 0; if(vis[x][y])return MAXN; if(dis[x][y] != -1) return dis[x][y]; vis[x][y] = 1; if(mp[x][y] == -1) { vis[x][y] = 0; dis[x][y] = 0; return 0; } else { int tmp = dfs1(x + xx[mp[x][y]],y + yy[mp[x][y]]) + 1; vis[x][y] = 0; dis[x][y] = tmp; return tmp; } } int dfs2(int x,int y,int cnt) { if(bb[x][y] != -1) { if(bb[x][y] != cnt || mp[x][y] == -1)return 1; else return 0; } if(mp[x][y] == -1) { bb[x][y] = cnt; return 1; } else { bb[x][y] = cnt; return dfs2(x + xx[mp[x][y]],y + yy[mp[x][y]],cnt + 1); } } void cal() { ans = 0; int mark; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(mp[i][j] == -1)continue; if(dis[i][j] != -1)continue; int tmp = dfs1(i,j); if(tmp >= MAXN){ans = MAXN;return;} ans = max(ans,tmp); } } if(ans == 0)return ; mark = 0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(dis[i][j] == ans) { if(dfs2(i,j,1))mark++; if(mark > 1){ans *= 2;return ;} } } } ans += (ans - 1); } void output() { if(ans >= MAXN)puts("-1"); else cout<<ans<<endl; } int main () { while(true) { init(); if(input())return 0; cal(); output(); } }
Codeforces Round #224 (Div. 2) D 暴力搜索加记忆化,布布扣,bubuko.com
Codeforces Round #224 (Div. 2) D 暴力搜索加记忆化
原文:http://blog.csdn.net/yitiaodacaidog/article/details/38498675