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"); } } }.