题目链接
题目描述
You are given a matrix A of size N×M. You should partition the matrix in square submatrices such that each submatrix contains cells having the same value. Even more, all the cells having the same value should be part of the same square. Find out if it’s possible or not to do this.
输入
The first line contains two integers N and M.
Each of the next N lines contains M integers representing the elements of the matrix A.
1<= N,M <=300
0<= Ai,j <=1e5

输出
Print 1 if there is a solution, otherwise print 0.
样例输入 Copy
3 3
1 1 2
1 1 3
4 5 6
4 4
1 1 3 3
1 1 3 3
2 2 4 4
2 2 4 4
2 5
1 1 1 2 2
1 1 1 2 2
3 3
1 1 1
1 2 1
1 1 1
3 3
1 1 2
1 1 3
4 5 1

题意：给你n*m的矩阵，让你可以任意构成一个子矩阵，并且子矩阵的每个位置的值都相同，问你是否能完成，能输出1，不能输出0；
解题思路：数据比较小，我们可以直接暴力枚举，先找矩阵，然后标记，使得我们找到的每个子矩阵的值都不相同，一旦相同必然不行。

#include<stdio.h>
#include<string.h>
#include<map>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int mp[1005][1005];
int vis[100005];
int vvs[1005][1005];
int n,m;
int ddg()
{
    for(int i=1; i<=n; i++)//输入矩阵
    {
        for(int j=1; j<=m; j++)//
        {
            if(vis[mp[i][j]]==0)//标记
            {
                vis[mp[i][j]]=1;
                int hh,gg;
                int kk=mp[i][j];标记一个值
                int qw=0,we=0;
                for(hh=i; hh<=n; hh++)//查找子矩阵
                {
                    if(mp[hh][j]!=kk)//不相同则说明找到子矩阵
                    {
                        break;
                    }
                    else
                    {
                        qw++;
                    }
                }
                for(gg=j; gg<=m; gg++)
                {
                    if(mp[i][gg]!=kk)
                    {
                        break;
                    }
                    else
                    {
                        we++;
                    }
                }
                qw--;
                we--;
                if(qw==we)
                {
                    for(int hj=i; hj<=i+qw; hj++)
                    {
                        for(int hk=j; hk<=j+we; hk++)
                        {
                            if(mp[hj][hk]!=kk)
                            {
 
                                return 0;
                            }
                            else
                            {
                                vvs[hj][hk]=1;
                            }
                        }
                    }
                }
                else
                {
                    return 0;
                }
 
            }
            else
            {
                if(vvs[i][j]==0)
                {
                    return 0;
                }
            }
        }
    }
    return 1;
}
int main()
{
 
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        memset(vvs,0,sizeof(vvs));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                scanf("%d",&mp[i][j]);
            }
        }
        printf("%d\n",ddg());
    }
    return 0;