OCR识别题解

可以发现的不同之处在于没有环，有一个环，有两个环，那么只需要判断有多少个环就可以就可以判断不同的字母了。我们先把输入的图拆分成单个的数字(通过空白列),然后去先把数字周围'.'去掉(dfs边缘)，再去挨着遍历图，如果出现'.'就把这个'.'点及周围的所有'.'都标记,统计进行的次数来求得答案。时间复杂度，空间复杂度。

const int N=550;
char s[N][N],mp[N][N],ans[N];
int cnt[N];
bool vis[N][N];
vector<int> v;
void dfs(int x,int y,int n,int m) {
    if(x<1||y<1||x>n||y>m||vis[x][y]||mp[x][y]=='#')return ;
    vis[x][y]=1;
    dfs(x-1,y,n,m);
    dfs(x+1,y,n,m);
    dfs(x,y-1,n,m);
    dfs(x,y+1,n,m);
}
int gao(int n,int m) {
    memset(vis,0,sizeof vis);
    int sum=0;
    for(int i=1;i<=n;i++) dfs(i,1,n,m),dfs(i,m,n,m);
    for(int i=1;i<=m;i++) dfs(1,i,n,m),dfs(n,i,n,m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) if(!vis[i][j]&&mp[i][j]=='.'){
            sum++;
            dfs(i,j,n,m);
        }
    if(sum==0)return 1;
    if(sum==1)return 0;
    return 8;
}
class Solution {
public:
    /**
     * 
     * @param Picture string字符串vector Picture
     * @return string字符串
     */
    string OCR(vector<string>& Picture) {
        // write code here
        for(int i=0;i<Picture.size();i++) 
            for(int j=0;j<Picture[i].length();j++)
                s[i+1][j+1]=Picture[i][j];
        int n=Picture.size(),m=Picture[0].length();
        for(int i=1;i<=m;i++) for(int j=1;j<=n;j++)
            cnt[i]+=s[j][i]-'.';
        v.push_back(0);
        for(int i=1;i<=m;i++) if(!cnt[i])
            v.push_back(i);
        v.push_back(m+1);
        for(int x=1;x<v.size();x++) {
            for(int i=1,k=1;i<=n;i++,k++)
                for(int j=v[x-1]+1,h=1;j<v[x];j++,h++)
                    mp[k][h]=s[i][j];
            ans[x]='0'+gao(n,v[x]-v[x-1]-1);
        }
        string ss=ans+1;
        return ss;
    }
};