AOJ 0069 Drawing Lots II

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0069

概要

あみだくじに、新しく1本線を引いてゴールに行けるか。

解法

左上から、線引けるところを全探索

コード

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;

int n, m, g, d;

int check(int line[30][10])
{
    int now = m-1;
    for (int i = 0; i < d; i++) {
        now += line[i][now];
    }
    return (now == g - 1) ? 1 : 0;
}

int main()
{
    while (1) {
        int line[30][10] = { 0 };
        string s;
        int flag = 0;
        // 入力
        cin >> n;
        if (n == 0) break;
        cin >> m >> g >> d;
        memset(line, 0, sizeof(line));
        for (int i = 0; i < d; i++) {
            cin >> s;
            for (int j = 0; j < s.size(); j++) {
                if (line[i][j] != 0) continue;
                line[i][j] = s[j] - '0';
                line[i][j+1] = -(s[j] - '0');
            }
        }
        // 線を引かない
        if (check(line)) {
            puts("0");
            continue;
        }
        // 線を引く
        for (int i = 0; i < d; i++) {
            for (int j = 0; j < n; j++) {
                if (line[i][j] != 0) continue;
                if (j > 0 && line[i][j - 1] == 1) continue;
                if (line[i][j + 1] != 0) continue;
                // 引く
                line[i][j + 1] = -1;
                line[i][j] = 1;
                // 調べる
                if (check(line)) {
                    printf("%d %d\n", i + 1, j + 1);
                    flag = 1;
                    break;
                }
                // 戻す
                line[i][j + 1] = 0;
                line[i][j] = 0;
            }
            if (flag) break;
        }
        if (flag == 0) {
            puts("1");
        }
    }
    return 0;
}