标签：cnt int 矩阵 3005 && x2 y2
- 通过矩阵转置，归并行、列两种情况
- 先行后列表示坐标
点击查看代码
#include <bits/stdc++.h>
using namespace std;
char c[3005][3005];
int s[3005][3005],u,v,n,m,l[3005],r[3005];
bool f;
int calc(int x1,int y1,int x2,int y2)
{
return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}
void solve1()
{
for(int i=1;i<=n;i++)
{
if(c[i][v]=='.'||c[i][v]=='S')
{
l[i]=r[i]=v;
while(c[i][l[i]-1]=='.'||c[i][l[i]-1]=='S')
{
l[i]--;
}
while(c[i][r[i]+1]=='.'||c[i][r[i]+1]=='S')
{
r[i]++;
}
}
}
int x1=u;
for(int x2=1;x2<x1;x2++)
{
if(c[x2][v]!='#')
{
bool f1=false,f2=false;
int cnt=0;
for(int y=max(l[x1],l[x2]);y<=min(r[x1],r[x2]);y++)
{
if(calc(x2,y,x1,y)==x1-x2+1)
{
f1|=(y<=v);
f2|=(y>=v);
cnt++;
if(f1&&f2&&cnt>=2)
{
f=true;
break;
}
}
}
}
}
for(int x2=x1+1;x2<=n;x2++)
{
if(c[x2][v]!='#')
{
bool f1=false,f2=false;
int cnt=0;
for(int y=max(l[x1],l[x2]);y<=min(r[x1],r[x2]);y++)
{
if(calc(x1,y,x2,y)==x2-x1+1)
{
f1|=(y<=v);
f2|=(y>=v);
cnt++;
if(f1&&f2&&cnt>=2)
{
f=true;
break;
}
}
}
}
}
}
void solve2()
{
for(int i=1;i<=m;i++)
{
if(c[u][i]=='.'||c[u][i]=='S')
{
l[i]=r[i]=u;
while(c[l[i]-1][i]=='.'||c[l[i]-1][i]=='S')
{
l[i]--;
}
while(c[r[i]+1][i]=='.'||c[r[i]+1][i]=='S')
{
r[i]++;
}
}
}
int y1=v;
for(int y2=1;y2<y1;y2++)
{
if(c[u][y2]!='#')
{
bool f1=false,f2=false;
int cnt=0;
for(int x=max(l[y1],l[y2]);x<=min(r[y1],r[y2]);x++)
{
if(calc(x,y2,x,y1)==y1-y2+1)
{
f1|=(x<=u);
f2|=(x>=u);
cnt++;
if(f1&&f2&&cnt>=2)
{
f=true;
break;
}
}
}
}
}
for(int y2=y1+1;y2<=m;y2++)
{
if(c[u][y2]!='#')
{
bool f1=false,f2=false;
int cnt=0;
for(int x=max(l[y1],l[y2]);x<=min(r[y1],r[y2]);x++)
{
if(calc(x,y1,x,y2)==y2-y1+1)
{
f1|=(x<=u);
f2|=(x>=u);
cnt++;
if(f1&&f2&&cnt>=2)
{
f=true;
break;
}
}
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c[i][j];
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(c[i][j]!='#');
if(c[i][j]=='S')
{
u=i;
v=j;
}
}
}
solve1();
solve2();
if(f==true)
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
return 0;
}
/*
(x1,y1) (x1,y2)
(x2,y1) (x2,y2)
*/
标签：cnt,
int,
矩阵,
3005,
&&,
x2,
y2
From： https://www.cnblogs.com/watersail/p/18370913