// Problem and solution written by Thomas Tang #include #include #include #include typedef struct { int row, col; } Pos; int numPoints(int n) { return 3*n*n - 3*n + 1; } int numCol(int n, int row) { return 2*n - 1 - abs(n-1-row); } int pos2index(int n, Pos p) { int row, index; for (index = 0, row = 0; row < p.row; row++) { index += numCol(n, row); } return index + p.col; } Pos index2pos(int n, int index) { Pos p; for (p.row = 0; p.row < 2*n-1; p.row++) { if (index - numCol(n, p.row) < 0) break; index -= numCol(n, p.row); } p.col = index; return p; } int isLegalPos(int n, Pos p) { return ((p.row >= 0) && (p.row < 2*n-1)) && ((p.col >= 0) && (p.col < numCol(n, p.row))); } void findNeighbour(int n, int index, vector& neighbour) { int drow[6], dcol[6], i; Pos p, np; neighbour.clear(); p = index2pos(n, index); /* top */ drow[0] = drow[1] = -1; if (p.row < n) { dcol[0] = -1; dcol[1] = 0; } else { dcol[0] = 0; dcol[1] = 1; } /* side */ drow[2] = drow[3] = 0; dcol[2] = -1; dcol[3] = 1; /* bottom */ drow[4] = drow[5] = 1; if (p.row < n-1) { dcol[4] = 0; dcol[5] = 1; } else { dcol[4] = -1; dcol[5] = 0; } for (i = 0; i < 6; i++) { np.row = p.row + drow[i]; np.col = p.col + dcol[i]; if (isLegalPos(n, np)) { neighbour.push_back(pos2index(n, np)); } } } main() { int n, start, step; int i, j, k; while (scanf("%d%d%d", &n, &start, &step) == 3) { if ((n == 0) && (start == 0) && (step == 0)) break; vector tried; vector current, previous; for (i = 0; i < numPoints(n); i++) { tried.push_back(false); } tried[start] = true; current.push_back(start); for (i = 0; i < step; i++) { previous = current; current.clear(); for (j = 0; j < previous.size(); j++) { vector thisOne; findNeighbour(n, previous[j], thisOne); for (k = 0; k < thisOne.size(); k++) { if (!tried[thisOne[k]]) { current.push_back(thisOne[k]); tried[thisOne[k]] = true; } } } } sort(current.begin(), current.end()); printf("%d", current.size()); for (i = 0; i < current.size(); i++) { printf(" %d", current[i]); } printf("\n"); } }