栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 2958 Correct the digit

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 2958 Correct the digit

#include<iostream>#include<set>#include<map>#include<cstring>#include<cstdlib>#include<stdio.h>using namespace std;enum {    SIZ = 104,};map<int, int> tab;map<int, set<int> > mis;char digStr[4][40] = {    "._....._.._....._.._.._.._.._.",    "|.|..|._|._||_||_.|_...||_||_|",    "|_|..||_.._|..|._||_|..||_|._|"};char buf[20];int parse(char s[][40], int p){    int j;    for (j=0; j<3; ++j){        strncpy(&buf[j*3], &digStr[j][3*p], 3);    }    buf[9] = 0;    int v = 0;    for (j=0; j<9; ++j){        v <<= 1;        if (buf[j]!='.'){ v |= 1;        }    }    return v;}void mistake(int v, int i){    for (int p=1,j=0; j<10; p<<=1, ++j){        if (v & p){ int nv = v & ~p; mis[nv].insert(i); mistake(nv, i);        }    }}void makeTable(){    for (int i=0; i<10; ++i){        int v = parse(digStr, i);        tab[v] = i;        mistake(v, i);    }}int ansCnt;char save[20];char rest[20];int val[20];void dfs(int p, int d){    if (d >= 9){        rest[d] = 0;        int v = 0;        for (int i=0; i<9; ++i){ v += (9-i)*(rest[i]-'0'); v %= 11;        }        if (v == 0){ ++ansCnt; if (ansCnt){     strcpy(save, rest); }        }        return;    }    map<int, int>::iterator it = tab.find(val[d]);    if (it != tab.end()){        rest[d] = it->second + '0';        dfs(p, d+1);        if (ansCnt >= 2) return;    }    if (p == 0){        map<int, set<int> >::iterator sit;        sit = mis.find(val[d]);        if (sit != mis.end()){ set<int> &s = sit->second; for (set<int>::iterator si=s.begin(); si!=s.end(); ++si){     rest[d] = *si + '0';     dfs(1, d+1);     if (ansCnt >= 2)         return; }        }    }}void fun(){    ansCnt = 0;    for (int i=0; i<9; ++i){        val[i] = parse(digStr, i);    }    dfs(0, 0);    if (ansCnt == 0){        printf("failuren");    } else if (ansCnt >= 2){        printf("ambiguousn");    } else {        printf("%sn", save);    }}int readIn(){    int i;    for (i=0; i<3; ++i){        if(scanf("%s", digStr[i]) < 0) return 0;    }    return 1;}int main(){    makeTable();    while(readIn() > 0){        fun();    }    return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/380153.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号