题意，给你迷宫算出其中个封闭空间的个数，以及求出所有封闭的空间的最大步长，但是给你的迷宫式“/”,“\”来标记的所以需要将每个格子分开来3*3的格子来算，
一开始按照2*2来算，2*2有临界情况不好算（233333）……
格式需要额外空一行……
题很简单，就是dfs走出边界说明不是封闭的……
不过就这样了……还是太弱了……
话说，今天又颓了一天……
233333333
代码……
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <cctype>
#include <string>
#include <malloc.h>
#include <queue>
#include <map> using namespace std;
const int INF = 0xffffff;
const double Pi = * atan();
const int Maxn = + ;
//int dir2[8][2] = {{-1,0},{0,-1},{-1,1},{1,-1},{-1,-1},{1,0},{0,1},{1,1}};
int dr[] = {,,-,,-,,-,};
int dc[] = {,,,-,,-,-,}; bool graph[][];
int w,h;
int num;
bool flag; void dfs(int r,int c){
if(r < || c < || r > *h- || c > *w- ){
flag = ;
return;
}
if(graph[r][c])
return;
graph[r][c] = ;
num++;
for(int i = ;i < ;i++){
int xx = r + dr[i];
int yy = c + dc[i];
dfs(xx,yy);
}
} int main()
{
#ifndef ONLINE_JUDGE
freopen("inpt.txt","r",stdin);
#endif
int cas = ;
while(cin >> w >> h){
if(!w && !h)
break;
cout << "Maze #" << ++cas << ":" << endl;
if(!w || !h){
cout << "There are no cycles." << endl << endl;
continue;
}
char str[];
memset(graph,,sizeof(graph));
for(int i = ;i < h;i++){
cin >> str;
for(int j = ;j < w;j++){
if(str[j] == '\\'){
graph[*i][j*] = graph[*i+][*j+] = graph[*i+][*j+] = ;
}
else if(str[j] == '/'){
graph[*i][j*+] = graph[*i+][*j+] = graph[*i+][*j] = ;
}
}
}
/* for(int i = 0;i < 3*h ;i++){
for(int j = 0;j < 3*w;j++)
cout << graph[i][j];
cout << endl;
}*/
int cnt = ;
int road = -;
for(int i = ;i < *h;i++){
for(int j = ;j < * w;j++){
if(!graph[i][j]){
flag = ;
num = ;
dfs(i,j);
if(flag)
continue;
cnt++;
if(num > road)
road = num;
}
}
}
if(cnt == )
cout << "There are no cycles." << endl;
else{
cout << cnt << " Cycles; the longest has length " << road/ << "." << endl;
}
cout << endl;
}
return ;
}
测试用例：
\//\\/
\///\/
//\\/\
\/\/// ///
\//
\\\ /\/\/
\/\/\
/\/\/
/\/\/
\/\/\ //\\
//\\
\\//
\\// /\/\/\
\//\\/
///\\\
\\\///
/\\//\
\/\/\/ /\/\/\
\\/\//
//\/\\
\/\/\/ /\/\/\
\\/\//
//\/\/
\/\/\/ \\\//\/\\/////\//\\\\\\/\//\\\\//\//////\\\/\//\/\\/\\/\/\//\/\/\\\/\/\ \//\
//\\\/\/\\\//\/\\\/\/\/\\\/\/\/\\//\/\\\/\\/\/\//\\/\///////\//\/\\///\/ \\/
/\\//\///\\\\/////\//\/\///\\\\/\//\/\\/\\\\\\/\////\\\\//\\////\/\\\/\/ \\\
\\\//\\\/\\/\/\/\\/\/\\\\/\\\\//\\\/\/\\/\\\\\\\\/\\/\////\\//\\\//\/ \///\\
/\\//\/\/\/\\\//\/\/\\/\\/\\\\\//\\/\\///\\/\\\///\\//\\///\//////\\//\/ \\/
\\\\\//\\\\/\\/\///\\/\/\\/\///\////\/\\\/\\/\/\/\\\/\\\\/////\\\\//\\\ \//\
\///\/\/\\//\\\\/\\\\//\/\//\\/\///\\\\\\\/\\\\/\/\\\//\\/\\//\///\/\\ \//\/
\\/\\//////\//\\/\/\\\\\\//\\\\//\//\//\/\/\/\/\\//\\/\///\//\\\\\/\\//\ \\\
//\\/\//\\//\//\//\/\\///\\/\/\////\\/\\///\////\/\\///\\/\///\\\\//\\/ \///
\//\////\///\\\\\\\///\//\/\///\\/\/\\\\///\\\/\\\///\\\/\\//\\/\\/\//\/ \\\
/\\//\\///\\\\\\///\////\///\/\/\\\//\\/\\/\////\/\\/\/\////\/\/\\/\/\/ \/\/
/\/\\\\\/\\/\/\\/\\///\\//\//\/\//\//\////////\////\\/\\\\\\\///\\////\ \/\\
/\//\\/\\\/\\/\//\\\\\/\\\////\//\\/\\\\\\\/////\\\////\/\\//\/\\\\\/\// \\\
\/\\/\//\\\//\/\\\/\\///\\\\\\\\/\\\//\\\///\\\/\\\/\\\\\\/\/\\/\/\/\/\/ \/\
//\\//\\/\\//\\\\///\\\\\\\/\\///\\//\///\//////\/\//\/\\\\/\\/\//\\/\/ \///
\\/\/\//\/\//\\///\\\\\/\///////////\///\\/\/\//\/\///\/\\\/\/\\/\\\\\/\ \/\
///\\\\///\/\//\\\\\/\/\\\\///\\\/\\\\\\\\\\///\\\\\/\///\\/\/\///\\\\\ \/\/
\//\\\\\/\////\\\/\\\/\\\\/\/\//\////\\//\//////\/\//\\/\///\/\/\\///\ \///\
/\\/\\\\\\\\\\\\//\\\///\///\\/\\\\///\////\\///\//\/////\\\//\//\\/\\\/ \\/
//\/////\\/\\\\/\\\/\\//\\\\\//////\//\\/\////\///\\\\//\////\/\/\/\/// \//\
//\\\\\/\//\//\\\\\\///\\\/\/\////\/\/\\\\\/\///\/\\\///\\//\\\/\/\\//\/ \/\
\\/\\\/\\//\///\\//\\\\\\/\/\\///////\/\//\\\/\\////\\\\\/\\\/\\/\/\//// \\\
/\\//\\\\/\/\/\\/\\/\/\\///\////\\\//\/\\//\\/\///\/\\//\\/\////\//\\/\\ \\\
\\/\//\\///\/\/\//\//\\\\\//\/\\/\/\//\\///////////////\/\\/\\\/\\\\/\\/ \//
//\//\////\///\/\/\/\///\\//\\/\\//\//\\/\//\/\/\//\\\\\\///\/\\\\\\//\/ \\/
\\//\//\\//\\/\\\\/\\\\\/\\/\\//\/\\\/\//\\\///\\/\\\/\\//\\/\\/\///\/\\ \/\
/\//\//\/\\\/\\///\\\/\\/\/\\///\\\\///\//\/\\\\///\\\\/\\/\\\/\///\/\\ \//\
\//\\//\///\/\/\\\\/\\/\\\\\\////\\\\/\\\///\\/\\/\\\\\\/\//\\/\\//\/\// \//
//\\\/\///\/\\\\\/\\//\////\\//\\//\/\//\\/////\\\/\\\/////\\//\/\/\\\/\ \\/
//\/\\/////\\\\\\////\\\\/\\/\//\/\\//\\\//\/\///\\/\\\\//\///\//\///\/\ \\/
//////\/\///\\\///////\\\/\/\\//\\\//\\\\\\/////\//\/\/////\\//\\/\/\/\/ \/\
/\/\///\\//\///\\\\\/\\/\\////\/\/\/\//\//\\///\///\\/\/\/\/\\\\//\/\\ \//\\
\\/\/\//\\\//\\//\///\\\/\\//\///\/\////\/\/\\\/\//\\\///\/\/\\/\///\\ \///\
\//\//\\/\///\/\/\\/\/\\\\///\\/////\/\\///////////\/\\\\/\\\\\/\///// \///\
/\///\\\////\\\\/\/\\\///\//\\\\\\/\///\\//\//////\\/\\/\\\/\\\\\\/\//\ \///
\/\////\/\///\\///\///\\\/\\\/\/\\/\/\\\\/\\\\/////\\\\////\///\\\/\///\ \//
/\\//////\/\////\/\///\\\/\///\\\\//////\\/////\/\////\\/\/////\\//\//\ \/\\
/\/\/\\///\\\\///\\//\/\/\/\////\//\//\\/\//\//\/\////\/\////\\/\//\\\\ \/\\
/\\\\\/\/\/\/\\\/\\\//\\/\\/////\/\/\\//\\/\/\//\/\/\\////\//\//\/\\/\\ \/\\
\\/\\\/\/\\\/\\\////////\\//\\/\///\/\/\////\//\\/\\\\\\\\//\\\\/\\\\\\/ \//
//\/\/\//\/\/\/\\/\/\\/\\\/\//\//////\//\\\\\\\///\\/\//////\\/\\////\\\ \/\
////\/\\/\\///\\\\///\/\//\\/\/\//\\/\//\/\\/\//////\//\/////\/\\\/\\/\ \/\\
//\/\//\\/\//\/\\\\//\\//\/\//\\\///\//\\\///\\\\/\\//\\\\//\//\\\\/\\/\ \/\
/\\\\////\\//\\\/\\\\\///\\\\\/\\\\\///\\\/\//\\\\//\\/\///////\/\//\ \/////
//\\\\\\/\/\\/\\\/\/\\\\//\//\\/\\\\/\/\\\/\//\/\/\/\\\////\/\\///\/\/ \//\\
///\/\///\\/\\/\/\/\///\//\///\////\\//\\/\/\//\\\////\////\////\\\\/\ \///\
\\\//\//\\\\\//\//\\////\//\\///\/\/\\\/\//\/\\\//\\\/\\\\//\\/\//\// \/////
\/\\\\\\\\\/\//\\\/\\\\\/\\\/\\/\/\/\/\/\\\\/////\//\\\/\\\\\\/\\/\\\\\ \/\/
//\/////\/\/\\///////\\//\\\\\\////\\////\/\//\///\\\\//\/\\\\\\\//\/\\\ \//
\\/\/\\\//\//\\\//\/\\\\/\\/\\///////\///\\/\\\/\///\\///////\\\/\\\\\\\ \//
\\//\/\//\\//\\//\\\\\\/\\\/\/\\/\\\\\//\\\\/\/\//\//\///\\\\/\\//\////\ \\/
/\\/\/\//\//\\\/\//\\/\/\\\\\\/\\//\/\\/\\///\/\\\//\\//\\/\\\\////\//\ \///
///\\\\/\/\\\\/\\///\\\//\/\//\//\\\//\\///\////\/\//\\\///\//////\\\\\/ \\\
/\\\/\////\///\\\\///\\\\/\/\\\\\/\//\\/\\//////\\\\\/\\/\//\///\\/\\\/\ \\/
\\\//\\\\\\/\\\//\\//\//\/\\//\\\////\\/\/\/\\/\\\///\///\/\\/\\\/\/\// \//\
\/\\\/////\\////\////\\\//\\/\\/\/\\\/\/\/\/\/\///\////\\\///\\//\/\/\// \\/
//\/\///\\//\/\\////\///\\/\////\/\///\\\//\//////\\\\\/\\/\\\/\\/\\\\\/ \//
//\/\//\\/\///\\/\\///\///\//\/\\//////\//\\\\/\///////\\\////\\/\//\// \//\
//\\\/\\/\/\/\\/\/\/\//\\\/\//\//\\\\/\//\\\\\\/\////\\\/\\\/\\//\//\/\\ \//
\/\\/\\\\/\//\/\\/\/\\\//\\\\/\//\\/\/\\\\\///\\\\\/\\\/\/\\/\\\\\\/\/\/ \/\
\\///\/\/\///\/\\\\\/\\/\//////\/\///\/\/\\/\/\\//\/\//\//\\\\/\\\\///\/ \/\
/\/\/\\\\/\///\\/\/\\/\/\\\\/\/\/\//\\\\\/////\//\\//\\/\\\///\\\//\\\/\ \\\
/\\\\//\///\//\/////\/\\/////\/\/\\\\/\\//\//\\\\\/\////\\\\/\\/\////\\ \//\
\/\/\///\//\\\\\/\\\\\///\//\\////\\\\\/\/////\\\/\\//\\\///\///\//\///\ \\/
\///\\\////\/\\/\/\\//\/\////\\\\/\\\/\\/\\\\\\\//\\////\/\\\\\\///\//\/ \//
/\/\//\///\//////\\\/\\/\///\/\/\//\\/\/\\////\\\\\\/\/\\\//\/\\/\\\/\// \\\
/\\//\\\//////\\/\\///\/\/\\/\/\////\\/\\\/\\//////////\///\/\\/\\\/\\\ \/\/
///\//\/\\//\/\//\//\///////\\\//\\\\//\/\/\\//\\/\//////\\\\\\\///\/\\/ \//
\\///\/\\\/\//\///\\\\\\/\\\\/\\/\\//\/\\\/\\\/\/\//\///\\///\/\///\//// \/\
\////\\////\\/\\\/\/\///\///\//\/\/\\/\/\/\\\///\\\\\///\/\\\/\\/\/\\\/ \//\
\\\/\/\\////\\///\//\\\\/\/\\\//\//\////\/\//\/\\\\\/\//\/\//////\\/\\// \\\
\////\\\/////\\\//\\\\//\\\\//\\/\\\\//\/\/\\\\/\///\//\\//\\\\//\/ \//////\
\\\\\//\\\/\\/\////\\//\\//\/\/\/\/////\\/\\//\///\\/\//\\\\\\\///\/\// \/\\
/\/\\//\//\/\\\/////\\\/\\\//\//\////\\///\/\//\\\\\/\/\//////\\/\\/\\/ \///
\/\//\//\//\\///\\\//\\////////\\\\//\//\//\\\/\\///\/\/\/\///\/\////\/\ \\/ //\\\
///\\
\\\\\
/\\//
\\\//
ans:
Maze #:
Cycles; the longest has length . Maze #:
There are no cycles. Maze #:
Cycles; the longest has length . Maze #:
Cycles; the longest has length . Maze #:
Cycles; the longest has length . Maze #:
Cycles; the longest has length . Maze #:
Cycles; the longest has length . Maze #:
There are no cycles. Maze #:
There are no cycles. Maze #:
Cycles; the longest has length . Maze #:
Cycles; the longest has length .