黑书上的【例题3】。
meet[l][r]代表l和r是否会相遇,显然meet[l][r]在r - l = 1时一定为真。
然后l和r能够相遇的条件是,能够找到一个k使得,l和k能相遇并且l可以打败k,r和k能相遇并且r能打败k。
处理环用了一贯的方法,长度扩展为两倍然后拆为链。
#include <algorithm> #include <stdlib.h> #include <string.h> #include <stdio.h> using namespace std; #define MAXN 110 int a[MAXN][MAXN]; int meet[MAXN << 1][MAXN << 1]; int live[MAXN], n, tot; bool dfs(int l, int r) { if (meet[l][r] != -1) return meet[l][r]; if (l + 1 >= r) return meet[l][r] = 1; for (int k = l + 1; k < r; ++k) if (dfs(l, k) && dfs(k, r) && (a[l % n][k % n] || a[r % n][k % n])) return meet[l][r] = 1; return meet[l][r] = 0; } int work() { scanf("%d", &n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) scanf("%1d", &a[i][j]); memset(meet, -1, sizeof(meet)); tot = 0; for(int i = 0; i < n; i++) if(dfs(i, i + n)) live[tot++] = i; printf("%d\n", tot); for(int i = 0; i < tot; i++) printf("%d\n", live[i] + 1); } int main() { // freopen("196.in", "r", stdin); int t; scanf("%d", &t); while(t--) { work(); } return 0; }