用 DFS 找一个环。
用一个 vis
数组加标记即可。
LL n, vis[N];
vector<LL> G[N];
LL T = 0;
LL vis2[N], tmp[N];
void Find(LL x){
if (vis2[x]){
cout << T << "\n";
for (LL i = 1; i <= T; i ++)
cout << tmp[i] << " ";
exit(0);
}
vis2[x] = 1;
++ T;
tmp[T] = x;
for (auto it : G[x]){
if (vis[it] >= 2)
Find(it);
}
return ;
}
void DFS(LL x){
++ vis[x];
if (vis[x] == 3){
Find(x);
exit(0);
}
for (auto it : G[x]){
DFS(it);
}
return ;
}
int main(){
Fcin;
cin >> n;
LL x;
for (LL i = 1; i <= n; i ++){
cin >> x;
G[i].emplace_back(x);
}
for (LL i = 1; i <= n; i ++){
memset(vis, 0, sizeof (vis));
if (vis[i])
continue;
DFS(i);
}
return 0;
}
暴力广搜,水。
LL n, m;
char G[1000][1000];
bool vis[1000][1000], res[1000][1000];
int main(){
Fcin;
cin >> n >> m;
for (LL i = 1; i <= n; i ++){
for (LL j = 1; j <= m; j ++){
cin >> G[i][j];
}
}
queue<pair<LL, LL> > q;
q.push(mkp(2, 2));
vis[2][2] = res[2][2] = 1;
while (!q.empty()){
LL x = q.front().first, y = q.front().second; q.pop();
LL t1 = x, t2 = y;
while (t1 > 1 && G[t1 - 1][t2] == '.'){
res[t1 - 1][t2] = 1;
t1 --;
}
if (t1 != x || t2 != y){
if (!vis[t1][t2]){
vis[t1][t2] = 1;
q.push(mkp(t1, t2));
}
}
t1 = x, t2 = y;
while (t1 < n && G[t1 + 1][t2] == '.'){
res[t1 + 1][t2] = 1;
t1 ++;
}
if (t1 != x || t2 != y){
if (!vis[t1][t2]){
vis[t1][t2] = 1;
q.push(mkp(t1, t2));
}
}
t1 = x, t2 = y;
while (t2 > 1 && G[t1][t2 - 1] == '.'){
res[t1][t2 - 1] = 1;
t2 --;
}
if (t1 != x || t2 != y){
if (!vis[t1][t2]){
vis[t1][t2] = 1;
q.push(mkp(t1, t2));
}
}
t1 = x, t2 = y;
while (t2 < m && G[t1][t2 + 1] == '.'){
res[t1][t2 + 1] = 1;
t2 ++;
}
if (t1 != x || t2 != y){
if (!vis[t1][t2]){
vis[t1][t2] = 1;
q.push(mkp(t1, t2));
}
}
}
LL Ans = 0;
for (LL i = 1; i <= n; i ++){
for (LL j = 1; j <= m; j ++)
Ans += res[i][j];
}
cout << Ans;
return 0;
}
提供一种二分做法。
对于每个格子二分一下它向右下延伸,最大的合法正方形边长 ,则答案就为 。
二分处理时,整个正方形有无洞口是可以用二维前缀和预处理得到的。
时间复杂度:
bool check(LL x, LL y, LL Len){
return (Pre[x + Len - 1][y + Len - 1] - Pre[x - 1][y + Len - 1] - Pre[x + Len - 1][y - 1] + Pre[x - 1][y - 1]) == 0;
}
int main(){
Fcin;
cin >> H >> W >> n;
LL x, y;
for (LL i = 1; i <= n; i ++){
cin >> x >> y;
Pre[x][y] = 1;
}
for (LL i = 1; i <= H; i ++){
for (LL j = 1; j <= W; j ++){
Pre[i][j] += Pre[i][j - 1];
}
for (LL j = 1; j <= W; j ++){
Pre[i][j] += Pre[i - 1][j];
}
}
LL cnt = 0;
for (LL i = 1; i <= H; i ++){
for (LL j = 1; j <= W; j ++){
LL L = 1, R = min(H - i + 1, W - j + 1), res = 0;
while (L <= R){
LL Mid = (L + R) >> 1;
if (check(i, j, Mid))
L = Mid + 1, res = Mid;
else
R = Mid - 1;
}
cnt += R;
}
}
cout << cnt;
return 0;
}