読者です 読者をやめる 読者になる 読者になる

AOJ0069 Drawing Lots II

問題
あみだくじ | Aizu Online Judge

あみだくじをする。縦棒の数と段の高さと、初めに選ぶ縦棒と当たりの縦棒の情報が与えられる。
この状態で当たりを引くことは出来るか。
また、一本だけ横棒を引くことが出来る。一本引いた場合に、あたりを引くことが出来れば、横棒を引いた場所を出力せよ。
なお、同じ段に隣接して横棒が引かれることはない。

解法
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;
}