AOJ 0069 Drawing Lots II

方針

制約から全通りシミュレーションしても余裕.
左か右に横線がある場合は置けないので注意する（このコードはテストケースが弱いから通ってしまったが）

ソースコード

#define FOR(i, a, b) for (int i = (a);i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

int n, m, answer, d;
char maze[32][16];

bool judge()
{
    int point = m - 1;

    for(int i = 0; i < d; i++)
    {
        if(point == 0)
        {
            if(maze[i][point] == '1')
            {
                point += 1;
            }
        }
        else if(point == n - 1)
        {
            if(maze[i][point - 1] == '1')
                point -= 1;
        }
        else
        {
            if(maze[i][point - 1] == '1')
                point -= 1;
            else if(maze[i][point] == '1')
                point += 1;
        }
    }

    if(point == answer)
        return true;

    return false;
}

int main()
{
    while(cin >> n, n)
    {
        scanf("%d%d%d", &m, &answer, &d);
        answer -= 1;

        REP(i, d)
            scanf("%s ", maze[i]);

        if(judge())
            puts("0");
        else
        {
            int x, y;
            bool f = false;
            for(int i = 0; i < d && !f; i++)
                for(int j = 0; j < n - 1 && !f; j++)
                {
                    if(maze[i][j] == '0' && !(maze[i][j - 1] == '1' || maze[i][j + 1] == '1'))
                    {
                        maze[i][j] = '1';
                        if(judge())
                        {
                            f = true;
                            x = j; y = i;
                            break;
                        }
                        maze[i][j] = '0';
                    }
                }
            if(f)
                printf("%d %d\n", y + 1, x + 1);
            else
                puts("1");
        }
    }
}.