Codeforces Round #208 (Div. 二)E. Dima and Kicks
http://codeforces.com/contest/358/problem/E
Dima is a good person. In fact, he's great. But all good things come to an end...
Seryozha is going to kick Dima just few times.. For this reason he divides the room into unit squares. Now the room is a rectangle n × mconsisting of unit squares.
For the beginning, Seryozha put Dima in a center of some square. Then he started to kick Dima (it is known, that he kicks Dima at least once). Each time when Dima is kicked he flyes up and moves into one of four directions (up, left, right, down). On each move Dima passes k (k > 1) unit of the length in the corresponding direction. Seryozha is really kind, so he kicks Dima in such way that Dima never meets the walls (in other words, Dima never leave the room's space). Seryozha is also dynamic character so Dima never flies above the same segment, connecting a pair of adjacent squares, twice.
Seryozha kicks Dima for a long time, but Dima is not vindictive — Dima writes. Dima marked all squares in which he was staying or above which he was flying. Thanks to kicks, Dima does not remember the k value, so he asks you to find all possible values which matches to the Dima's records.
The first line contains n and m (1 ≤ n, m ≤ 103) — size of the room.
Next n lines goes, each contains m numbers aij — Dima's notes: aij = 1, if Dima was staying in the square (i, j) or was flying above it. Otherwise aij = 0.
At least one aij equals 1.
In a single line in accending order print all k (k > 1), which matches the Dima's notes. If there are no such k and Dima invented this story with kicks, print -1.
5 5 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1
2 4
7 7 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0
2
3 3 1 1 1 1 1 1 1 1 1
-1
4 4 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
3
5 5 0 0 1 0 0 0 0 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0
-1
解析：欧拉回路
题意是说，有一个鸟按照每次朝一个方向, 以k units长度的方式飞行，飞过之后的格子是1，然后，给出飞过之后的矩阵，问k可能的取值。k>1
仔细分析,k>1,说明不能一个一个格子的飞行，至少是每次飞过2个边。所以，有两条规律：
①.不能出现
的情况，因为，如果四个1挨着，k>1是无法做到的，简单证明就是左上角和右下角的1的横坐标，可以用a*k, a*k+1 表示，而可以证明gcd(n,n+1)互素，也就是说两个相邻自然数最大公约数是1，因此k>1是无法做到的。
②.若出现
的情况，即，出现交叉的情况，无论交叉点的度数是3还是4，交叉点必停(2度节点如果是拐弯也必停)，即，鸟一定会在交叉点停歇。如果不停的话，横边飞过之后是无法达到竖边的。
另外，需要几个细节：
(A)图是连通图
(B)图中的交叉点一定构成欧拉图
(C)k的取值集合是所有边长的最大公约数的所有大于1的约数集。
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<cmath>
using namespace std;
#define N 1005
#define eps 1e-8
int n,m,amount;
int gcd;
int mat[N][N];
bool vis[N][N];
bool flaglen[N];
int GCD(int a,int b){
if(!b)return a;
else return GCD(b,a%b);
}
int existone(){
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
if(mat[i][j]&&mat[i][j+1]&&mat[i+1][j]&&mat[i+1][j+1])return 1;
return 0;
}
int searchconnected(int i,int j){
if(i<1 || i>n || j<1 || j>m)return 0;
if(!mat[i][j] || vis[i][j])return 0;
vis[i][j]=true;
return searchconnected(i+1,j)+
searchconnected(i-1,j)+
searchconnected(i,j+1)+
searchconnected(i,j-1)+1;
}
int connected(){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mat[i][j])
if(searchconnected(i,j)!=amount)return 0;
else return 1;
else continue;
}
int solve(){
int di[4]={0,0,1,-1};
int dj[4]={1,-1,0,0};
int t;
int cnt;
int cntodd=0;
memset(flaglen,0,sizeof(flaglen));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mat[i][j]){
cnt=mat[i-1][j]+mat[i+1][j]+mat[i][j-1]+mat[i][j+1];
cntodd+=cnt&0x01;
if(cntodd>=3)return 0;
if((cnt==2) && ( (mat[i-1][j]&&mat[i+1][j]) || (mat[i][j-1]&&mat[i][j+1]) ))continue;
else vis[i][j]=true;
}
gcd=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(vis[i][j])
for(int k=0;k<4;k++){
for(t=1;mat[i+di[k]*t][j+dj[k]*t] && !vis[i+di[k]*t][j+dj[k]*t];t++);
if(t>1){
flaglen[t]=true;
gcd=t;
}
}
for(t=max(n,m);t>1;t--)
if(flaglen[t])gcd = GCD(gcd,t);
//printf(">>%d\n",gcd);
return gcd!=1;
}
void print(int n){
for(int i=2;i<n;i++)
if(n%i==0)printf("%d ",i);
printf("%d\n",n);
}
int main()
{
scanf("%d%d",&n,&m);
memset(mat,0,sizeof(mat));
amount=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;amount+=mat[i][j],j++)
scanf("%d",&mat[i][j]);
if(existone() || !connected()){
printf("-1\n");
return 0;
}
if(solve()!=0)print(gcd);
else printf("-1\n");
// printf("%d\n",gcd);
// system("pause");
return 0;
}