AOJ0069 Drawing Lots II
あみだくじをする。縦棒の数と段の高さと、初めに選ぶ縦棒と当たりの縦棒の情報が与えられる。
この状態で当たりを引くことは出来るか。
また、一本だけ横棒を引くことが出来る。一本引いた場合に、あたりを引くことが出来れば、横棒を引いた場所を出力せよ。
なお、同じ段に隣接して横棒が引かれることはない。
解法
if(g[y][x]) x++;
else if(x && g[y][x-1]) x--;
というようにして、現在の段の高さyでループするシミュレーションをする。
一本引くことが出来るという制約は、入力の2次元配列で1が隣接しないような0である場所に1を宛がう全探索をすれば良い。段の高い方から選ぶので、左上からループすれば良い。
int m, k, a, d; vector<string> g; bool solve() { int x = k - 1; rep(y, d) { if(g[y][x]) x++; else if(x && g[y][x-1]) x--; } return x == a - 1; } int main() { while(cin >> m >> k >> a >> d && m) { g.clear(); g.resize(d); rep(i, d) cin >> g[i]; rep(i, d) for(auto& e: g[i]) e -= '0'; if(solve()) { cout << "0\n"; goto next; } rep(i, d) rep(j, m - 1) { if(!g[i][j] && (j == 0 || !g[i][j-1]) && (j + 1 == m - 1 || !g[i][j+1])) { g[i][j] = 1; if(solve()) { cout << i + 1 << " " << j + 1 << endl; goto next; } g[i][j] = 0; } } cout << "1\n"; next:; } return 0; }