#define it <> ::iterator
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <bitset>
#include <cstdio>
#include <vector>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const ll nex[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
const ll inf=0x7fffffff;
const ll mod=1e9+7;
ll n,a[1000001],f[1000001],siz[1000001],book[1000001],flag;
ll col=1,lst[3]={0,1,1};
char c;
map<ll,ll> mp;
ll p(ll x,ll y){
return (x-1)*n+y;
}
ll find(ll x){
return f[x]==x?x:f[x]=find(f[x]);
}
void merge(ll x,ll y){
ll fx=find(x),fy=find(y);
if(fx==fy)return ;
f[fx]=fy;
siz[fy]+=siz[fx];
siz[fx]=0;
return ;
}
void init(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!a[p(i,j)])continue ;
for(int k=0;k<4;k++){
ll dx=i+nex[k][0];
ll dy=j+nex[k][1];
if(dx<1||dy<1||dx>n||dy>n)continue ;
if(!a[p(dx,dy)])siz[find(p(i,j))]++;
}
if(i!=1)if(a[p(i,j)]==a[p(i-1,j)])merge(p(i,j),p(i-1,j));
if(j!=1)if(a[p(i,j)]==a[p(i,j-1)])merge(p(i,j),p(i,j-1));
}
}
return ;
}
bool check(ll x,ll y,ll col){
ll sum=0,tot=0;
mp.clear();
for(int k=0;k<4;k++){
ll dx=x+nex[k][0];
ll dy=y+nex[k][1];
if(dx<1||dy<1||dx>n||dy>n)continue ;
if(!a[p(dx,dy)])sum++;
else if(a[p(dx,dy)]==col){
siz[find(p(dx,dy))]--;
}
else if(a[p(dx,dy)]!=col){
if(siz[find(p(dx,dy))]==1)return 0;
siz[find(p(dx,dy))]--;
}
}
for(int k=0;k<4;k++){
ll dx=x+nex[k][0];
ll dy=y+nex[k][1];
if(dx<1||dy<1||dx>n||dy>n)continue ;
if(col==a[p(dx,dy)]){
if(!mp.count(find(p(dx,dy))))tot+=siz[find(p(dx,dy))];
mp[find(p(dx,dy))]=1;
}
}
if(!sum&&!tot){
for(int k=0;k<4;k++){
ll dx=x+nex[k][0];
ll dy=y+nex[k][1];
if(dx<1||dy<1||dx>n||dy>n)continue ;
if(!a[p(dx,dy)])continue ;
siz[find(p(dx,dy))]++;
}
return 0;
}
siz[find(p(x,y))]+=sum;
for(int k=0;k<4;k++){
ll dx=x+nex[k][0];
ll dy=y+nex[k][1];
if(dx<1||dy<1||dx>n||dy>n)continue ;
if(col==a[p(dx,dy)])merge(p(x,y),p(dx,dy));
}
return 1;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>c;
f[p(i,j)]=p(i,j);
if(c=='.')continue ;
book[p(i,j)]=1;
if(c=='X')a[p(i,j)]=1;
else if(c=='O')a[p(i,j)]=2;
}
}
init();
while(!flag&&lst[1]<n*n&&lst[2]<n*n){
for(int pos=lst[col];pos<=n*n;pos++){
if(book[pos])continue ;
ll x,y;
if(pos%n==0){x=pos/n;y=n;}
else {y=pos%n;x=(pos-y)/n+1;}
if(pos==n*n&&!check(x,y,col)){
flag=1;
break;
}
if(check(x,y,col)){
printf("%lld %lld\n",x,y);
lst[col]=pos+1;
book[pos]=1;
a[pos]=col;
break;
}
}
col^=3;
}
cout<<"-1 -1";
return 0;
}
记录