1

猫粮寸断 LV 10 @ 2017-09-06 18:57:26

//总体思路是一样的，但这是个非递归的实现
//判断无限爆炸，改到废，唉。。。
//为了让大家看的方便手动换了一下行，看懂就行
#include<iostream>
using namespace std;
int map[1010][1010];
int n,m,sum=0;
void dfs1(int y,int x)
{
    int chang=1,i,k;
    for(chang=1;x-chang>0&&x+chang<=m&&y-chang>0&&y+chang<=n;chang++)
    {   
        for(i=0;i<=chang;i++)
         if(map[y-chang][x-i]!=
                    map[y-chang][x+i]||
                    map[y-chang][x-i]!=
                    map[y+chang][x-i]||
                    map[y+chang][x-i]!=
                    map[y+chang][x+i]||
                    map[y+i][x-chang]!=map[y+i][x+chang])
          return ;
        for(i=0;i<=chang;i++)
         if(map[y+i][x-chang]!
                        =map[y-i][x-chang]||
                        map[y+chang][x+i]!=
                        map[y-chang][x+i]||
                        map[y-i][x+chang]!=map[y+i][x+chang])
          return ;
        sum++;
    }
    return ;
}

void dfs2(int y,int x)
{
    int chang=1,i,k;
    for(chang=1;x-chang>0&&x+chang+1<=m&&y-chang>0&&y+chang+1<=n;chang++)
    {   
        for(i=0;i<=chang;i++)
         if(map[y-chang][x-i]!
                    =map[y-chang][x+i+1]||map[y+chang+1][x-i]!
                    =map[y+chang+1][x+i+1]||map[y+i+1][x-chang]!
                    =map[y+i+1][x+chang+1])
          return ;
        for(i=0;i<=chang;i++)
         if(map[y+i+1][x-chang]!
                        =map[y-i][x-chang]||
                        map[y+chang+1][x+i+1]!=map[y-chang][x+i+1]||
                        map[y-i][x+chang+1]!=map[y+i+1][x+chang+1])
          return ;
        for(i=0;i<=chang;i++)
         if(map[y-chang][x-i]!=
                    map[y+chang+1][x-i])
          return ;
        sum++;
    }
    return ;
}
int main()
{
    int i,k;
    cin>>n>>m;
    for(i=1;i<=n;i++)
     for(k=1;k<=m;k++)
      cin>>map[i][k];
    sum+=n*m;
    for(i=1;i<=n;i++)
     for(k=1;k<=m;k++)
       dfs1(i,k);
    for(i=1;i<n;i++)
     for(k=1;k<m;k++)
      {
        if(map[i][k]==map
                     [i+1][k]&&map[i][k]==map[i][k+1]&&map[i][k]==map[i+1][k+1])
         {
           sum++;
           dfs2(i,k);
         }
      }
    cout<<sum;
    return 0;
}

逍遥♛子寒 @ 2019-03-14 20:56:50

QAQ不想看抽空来讲吧 QvQ

1

shiru LV 8 @ 2017-07-16 12:45:23

#include<iostream>
using namespace std;
long long a[1005][1005];
int main()
{
int m,n,t=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
int bian=2;
while(bian<=m&&bian<=n){
int bn=n+1-bian,bm=m+1-bian;
for(int i=1;i<=bn;i++){
for(int j=1;j<=bm;j++){
bool fan=true;
int x=i+bian-1,y=j+bian-1,midx=(x+i)/2,midy=(j+y)/2,hex=i+x,hey=j+y;
for(int p=i;p<=midx&&fan;p++){
for(int q=j;q<=midy&&fan;q++){
int duix=hex-p,duiy=hey-q;
if(a[p][q]!=a[duix][q]||a[p][q]!=a[p][duiy]||a[p][q]!=a[duix][duiy]){
fan=false;
}

}
}
if(fan) t++;
else fan=true;

}
}
bian++;
}
cout<<t+n*m;
return 0;
}

1

AlienUFO LV 8 @ 2009-06-29 08:20:55

数据有问题

357832

357821

0

Commander_X LV 8 @ 2017-05-10 19:12:53

哪个dalao能看看爆哪里了
#include <iostream>
#include <string>
using namespace std;

int n,m,w;
char a[101][101];
string b[101];//words
string d; //direction: 字母 A B C D E F G H 朝向上右上右右下下左下左左上
// 优先级顺序为D,C,B,A,H,G,F,E

// 检查方向
// p - 行, q - 列, r - 需要查找的字符串位置
bool check_D(int p, int q, int r)
{
int bl=b[r].length();
if(p+bl>n+1 || q+bl>m+1)
return false;

for(int i=0;i<bl;i++)
{
if(a[p+i][q+i]!=b[r][i])
return false;
}
return true;
}
bool check_C(int p, int q, int r)
{
int bl=b[r].length();
if(q+bl>m+1)
return false;

for(int i=0;i<bl;i++)
{
if(a[p][q+i]!=b[r][i])
return false;
}
return true;
}
bool check_B(int p, int q, int r)
{
int bl=b[r].length();
if(p-bl<0 || q+bl>m+1)//m原为n
return false;

for(int i=0;i<bl;i++)
{

if(a[p-i][q+i]!=b[r][i])
return false;
}
return true;
}
bool check_A(int p, int q, int r)
{
int bl=b[r].length();
if(p-bl<0)
return false;

for(int i=0;i<bl;i++)
{

if(a[p-i][q]!=b[r][i])
return false;
}
return true;
}
bool check_H(int p, int q, int r)
{
int bl=b[r].length();
if(p-bl<0 || q-bl<0)
return false;

for(int i=0;i<bl;i++)
{

if(a[p-i][q-i]!=b[r][i])
return false;
}
return true;
}
bool check_G(int p, int q, int r)
{
int bl=b[r].length();
if(q-bl<0)
return false;

for(int i=0;i<bl;i++)
{
if(a[p][q-i]!=b[r][i])
return false;
}
return true;
}
bool check_F(int p, int q, int r)
{
int bl=b[r].length();
if(p+bl>n+1 || q-bl<0)
return false;

for(int i=0;i<bl;i++)
{
if(a[p+i][q-i]!=b[r][i])
return false;
}
return true;
}
bool check_E(int p, int q, int r)
{
int bl=b[r].length();
if(p+bl>n+1)
return false;

for(int i=0;i<bl;i++)
{

if(a[p+i][q]!=b[r][i])
return false;
}
return true;
}

// 检查一个单词指定方向的全部位置
// r - 需要查找的字符串位置, d - 方向
bool check(int r, int d)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
bool t;
switch(d) {
case 'D':
t = check_D(i,j,r);
break;
case 'C':
t = check_C(i,j,r);
break;
case 'B':
t = check_B(i,j,r);
break;
case 'A':
t = check_A(i,j,r);
break;
case 'H':
t = check_H(i,j,r);
break;
case 'G':
t = check_G(i,j,r);
break;
case 'F':
t = check_F(i,j,r);
break;
case 'E':
t = check_E(i,j,r);
break; // ... 根据不同方向，调用不同的函数
}

if(t)
{
cout<<i<<j<<(char)d<<endl;
return true;
}
}
}

return false;
}

int main()
{
cin>>n>>m>>w;
//cout<<n<<m<<w;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
//cout<<a[i][j]<<" "<<i<<j<<endl;
}
}
for(int i=1;i<=w;i++)
{
cin>>b[i];
}

bool tf;
for(int k=1;k<=w;k++)
{
// ...按优先级顺序分别调用8次不同方向
if(check(k, 'D')) continue;
if(check(k, 'C')) continue;
if(check(k, 'B')) continue;
if(check(k, 'A')) continue;
if(check(k, 'H')) continue;
if(check(k, 'G')) continue;
if(check(k, 'F')) continue;
if(check(k, 'E')) continue;

}

}

0

alw008 LV 8 @ 2016-10-29 23:34:30

看后立马立了个flag，果然是个flag。全爆炸，求神牛帮看，谢！
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, ans=0;
int a[1005][1005];

void searchOdd(int c, int x, int y) {
int num;
if (x+c > n || x-c < 1 || y+c > m || y-c < 1) {
return ;
}

if (a[x-c][y+c] != a[x-c][y-c] || a[x-c][y-c] != a[x+c][y-c]) return ;
else {
num=a[x-c][y-c];
}
for (int i=x-c+1;i <= x+c;i++) {
if (a[i][y+c] != num || a[i][y-c] != num) {
return ;
};
}
for (int i=y-c+1;i <= y+c;i++) {
if (a[x-c][i] != num || a[x+c][i] != num) {
return ;
}
}

ans++;
searchOdd(c+1, x, y);
}

void searchEven(int c, int x, int y) {
int num;
if (x-c < 1 || x+1+c > n || y-c < 1 || y+1+c > m) {
return ;
}

if (a[x-c][y-c] != a[x+1+c][y-c] || a[x-c][y-c] != a[x-c][y+1+c]) {
return ;
} else {
num=a[x-c][y-c];
}

for (int i=x-c+1;i <= x+1+c;i++) {
if (a[i][y-c] != num || a[i][y+1+c] != num) {
return ;
}
}
for (int i=y-c+1;i <= y+1+c;i++) {
if (a[x-c][i] != num || a[x+c+1][i] != num) {
return ;
}
}

ans++;
searchEven(c+1, x, y);
}

int main() {
ios::sync_with_stdio(false);

cin >> n >> m;
for (int i=1;i <= n;i++) {
for (int j=1;j <= m;j++) {
cin >> a[i][j];
}
}

for (int i=1;i <= n;i++) {
for (int j=1;j <= m;j++) {
searchOdd(0, i, j);
searchEven(0, i, j);
}
}

cout << ans;

return 0;
}

0

zcq784951623 LV 8 @ 2016-05-12 19:03:08

#include<cstdio>
using namespace std;
int g[1100][1100];
int ans=0;
int n,m;
bool IN(int x,int y)
{
    return x>=1&&x<=n&&y>=1&&y<=m;
}
void dfs(int x1,int y1,int x2,int y2)
{
    if(IN(x1,y1)&&IN(x2,y2))
    {
        int l,r;
        l=x1;r=x2;
        while(l<=r)
        {
            if(g[l][y1]!=g[r][y1]||g[l][y2]!=g[r][y2]||g[l][y1]!=g[l][y2]||g[r][y1]!=g[r][y2])
                return;
            l++;
            r--;
        }
        l=y1;r=y2;
        while(l<=r)
        {
            if(g[x1][l]!=g[x1][r]||g[x2][l]!=g[x2][r]||g[x1][l]!=g[x2][l]||g[x1][r]!=g[x2][r])
                return;
            l++;
            r--;
        }
        ans++;
        dfs(x1-1,y1-1,x2+1,y2+1);
    }
}
int main()
{
//  freopen("P1556.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&g[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            dfs(i,j,i,j);
            dfs(i,j,i+1,j+1);
        }
    printf("%d",ans);
    return 0;
}

-1

zgx LV 10 @ 2009-10-02 21:43:10

貌似数据不够猛，如果全部都一样，那么楼下几位的算法应该就。。。。

-1

voyagec2 LV 10 @ 2009-07-26 16:46:11

MS预处理也可以

数据是随机的不会有很大的对称

-1

EZ_ray040123 LV 10 @ 2009-07-24 15:49:25

数奇边正方形：

1.枚举每个格

2.以该格为中心，每次加一圈得到一个更大的正方形，检验，如果不满足就枚举下一个格,否则加一圈，直到爆格

。

偶数的类似........

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 41ms

├ 测试数据 08：答案正确... 88ms

├ 测试数据 09：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：273ms

-1

oimaster LV 10 @ 2010-03-03 19:37:32

O(nm)的方法真难写，搞了近三小时。扩展KMP加上单调队列……

-1

牧云海 LV 10 @ 2009-06-28 22:41:15

首先要整明白题是什么意思。对称的正方形有两种，一种是中心是数的，另一种是中心是空的，也就是奇数长与偶数长的。之后先用几个Dp把关于每个点的各种参数求出来，比如上下方向最长对称是多少，左右是多少，关于这个点右下方的空的对称上下左右又是多少。之后对于每个点扫描两次（一次是点，一次是空），暴力循环就可以了。还有，注意细节！！很容易错的！！

这个题时限很宽，Vijos给了3s事实上我所有点总共也没用3s。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 41ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 119ms

├ 测试数据 09：答案正确... 197ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：438ms

-2

2mc LV 10 @ 2009-08-25 23:17:03

让大牛们一说成水题了。

我按EZ_ray大牛那样做的，不过判断时要注意

是

[]

的相等

而不是

||

这样

也不是

这样。

-2

LV 0 @ 2009-06-29 08:20:52

怀疑楼下怎么过的?

数据有错啊!

大家注意: 你算出来答案末尾是 832 的答案要减去 11 才能过!

-2

curimit LV 10 @ 2009-07-04 20:55:08

AC！卡内存过了！

-2

hhdllhflower LV 10 @ 2009-06-20 23:05:29

这题不难O(∩_∩)O~

但我没过╮(╯▽╰)╭

第十个数据：答案错误。。。。。

-3

LV 0 @ 2009-06-30 21:58:40

我是神牛！大家来膜拜我！！！！！

题解

16 条题解

也不是

对称的正方形

信息

状态

开发

支持

题解

16 条题解

也不是

对称的正方形

信息

状态

开发

支持

还没有账户？

登录