// Problem written by Albert Lai // This solution written by Thomas Tang #include #include #include #define SIZE 4 #define MAXDIR 8 typedef struct { int row, col; } Pos; char board[SIZE][SIZE+1]; // +1 for the \0 char pattern[20]; int ddir[MAXDIR][2] = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}}; // dir from 0 .. 7 bool givePos(Pos oldPos, int dir, Pos& newPos) { newPos.row = oldPos.row + ddir[dir][0]; newPos.col = oldPos.col + ddir[dir][1]; if ((newPos.row < 0) || (newPos.row >= SIZE) || (newPos.col < 0) || (newPos.col >= SIZE)) return false; return true; } bool ifUsed(Pos p, vector used) { int i; for (i = 0; i < used.size(); i++) { if ((used[i].row == p.row) && (used[i].col == p.col)) return true; } return false; } bool find(Pos p, vector used, int index) { int i; Pos newP; if (index == strlen(pattern)) return true; used.push_back(p); for (i = 0; i < MAXDIR; i++) { if (!givePos(p, i, newP)) continue; if (!ifUsed(newP, used) && (board[newP.row][newP.col] == pattern[index])) { if (find(newP, used, index+1)) { return true; } } } return false; } main() { int i, j; vector used; Pos p; while (scanf("%s", pattern) == 1) { for (i = 0; i < SIZE; i++) { scanf("%s", board[i]); } if (strlen(pattern) == 0) { printf("yes\n"); continue; } for (p.row = 0; p.row < SIZE; p.row++) { for (p.col = 0; p.col < SIZE; p.col++) { if (board[p.row][p.col] == pattern[0]) { if (find(p, used, 1)) { printf("yes\n"); goto done; } } } } printf("no\n"); done: i = 1; // dummy } }