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