SRM576 Div1 Easy - ArcadeManao
問題
h*wのグリッドがあり、(sx,sy)からx座標がh-1の任意のマスに行きたい
床があるマスとないマスがあり、床があるマスにしか移動することはできない
あるマス(x,y)からは、(x,y±1) には無条件で行ける (床さえあれば)
長さLのはしごを持っている場合は (x±L,y) にも行ける
最初にはしごの長さを選べるとき、目的達成に必要なはしごの長さの最小値を求めよ
1 <= h, w <= 50
解法
はしごの長さを全部試してBFSとかで適当に
class ArcadeManao { public: int shortestLadder(vector<string> s, int sx, int sy) { int h = s.size(), w = s[0].size(); sx--, sy--; rep(l,h) { bool v[55][55] = {}; queue<pair<int,int> > q; q.push({sx,sy}), v[sx][sy] = 1; while (!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); if (y+1<w && s[x][y+1]=='X' && !v[x][y+1]) v[x][y+1] = 1, q.push({x,y+1}); if (y-1>=0 && s[x][y-1]=='X' && !v[x][y-1]) v[x][y-1] = 1, q.push({x,y-1}); reps(i,max(0,x-l),min(h,x+l+1)) if (s[i][y]=='X' && !v[i][y]) v[i][y] = 1, q.push({i,y}); } rep(i,w) if (v[h-1][i]) return l; } return -1; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12504&rd=15496