問題背景
成語是中華民族的文化瑰寶，作為歷史的縮影、智慧的結(jié)晶、漢語言的精華，閃爍著睿智的光芒。
你的任務(wù)是給一個(gè)錯(cuò)誤的四字成語進(jìn)行糾錯(cuò)，找到它的正確寫法。具體來說，你只允許修改四個(gè)漢字中的其中一個(gè)，使得修改后的成語在給定的成語列表中出現(xiàn)。原先的錯(cuò)誤成語保證不在成語列表中出現(xiàn)。
有時(shí)，這樣的“糾錯(cuò)”結(jié)果并不惟一。例如“一糯千金”可以改為“一字千金”也可以改成“一諾千金”。但由于“糯”和“諾”是同音字，“一糯千金”實(shí)為“一諾千金”的可能性比較大。
因此，我們還將提供一個(gè)漢字分類表，要求修改前后的兩個(gè)字必須屬于同一個(gè)分類。
在這樣的限制下，我們保證成語糾錯(cuò)的結(jié)果惟一。
注意
1、漢字均采用GBK編碼(參見FAQ)
2、每個(gè)漢字分類至少包含兩個(gè)漢字，同一個(gè)漢字可能出現(xiàn)在多個(gè)類別中。
3、成語列表中的成語都是真實(shí)存在的四字成語。成語列表和待糾錯(cuò)成語中的所有漢字均在漢字分類表中的至少一個(gè)分類中出現(xiàn)。
輸入格式
輸入第一行包含兩個(gè)整數(shù)n, m(1<=n<=200, 1<=m<=20000)。n表示漢字類別的個(gè)數(shù)，m表示成語的個(gè)數(shù)。
以下n行每行用一個(gè)無空白分隔符（空格、TAB）的漢字串表示一個(gè)分類中的所有漢字。注意，該漢字串最多可能包含200個(gè)漢字。
以下m行為成語列表，每行一個(gè)成語，恰好四個(gè)漢字。
最后一行為待糾錯(cuò)的成語，恰好四個(gè)漢字，且不在成語列表中出現(xiàn)。
輸出格式
僅一行，為一個(gè)四字成語。在“修改必須在同一分類中進(jìn)行”的限制下，輸入數(shù)據(jù)保證糾錯(cuò)結(jié)果惟一。
樣例輸入
7 3
糯諾挪喏懦
字自子紫籽
前錢千牽淺
進(jìn)近今僅緊金斤盡勁
完萬
水睡稅
山閃衫善扇杉
一諾千金
一字千金
萬水千山
一糯千金
樣例輸出
一諾千金
解題思路
1、把漢字分類和正確成語分別放在字符串?dāng)?shù)組中，待糾錯(cuò)成語放在字符串里
2、把帶糾錯(cuò)成語對(duì)應(yīng)的正確成語找出來
3、對(duì)比找出待糾錯(cuò)成語中錯(cuò)的那個(gè)字，并保存錯(cuò)字位置索引
4、找到錯(cuò)字所屬的漢子類別，并保存類別的位置索引
5、根據(jù)錯(cuò)字的位置，判斷正確成語相應(yīng)位置的字是否在正確的漢字類別中，確定正確的成語輸出
【評(píng)價(jià)】這個(gè)題是第一題，我使用的方法是按部就班的進(jìn)行搜索計(jì)算，沒有太多的技巧，關(guān)鍵是把題目分析清楚。
參考代碼：
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <string.h>
int main(void)
{
int n(0);//漢字類別個(gè)數(shù) 1－200
int m(0);//正確成語個(gè)數(shù)1－20000
int i(0),j(0);//循環(huán)變量
int *tempLen;//漢字類的串長(zhǎng)
char** pClass=NULL;//存放漢字分類
char classBuffer[401];//緩存
char** pIdiom=NULL;//存放正確成語
char idiomBuffer[9];//緩存
char** pSet=new char*[200];//和待糾錯(cuò)成語有三個(gè)字相同的正確成語集合
char wrongString[9];//存放待糾錯(cuò)成語
scanf("%d",&n);
pClass=new char*[n];//n類
tempLen=new int[n];//長(zhǎng)度
scanf("%d",&m);
pIdiom=new char*[m];//m個(gè)成語
//讀漢字分類
for (i=0;i<n;i++)
{
scanf("%s",classBuffer);
tempLen[i]=strlen(classBuffer);
pClass[i]=new char[tempLen[i]+1];
memcpy(pClass[i],classBuffer,tempLen[i]+1);
}
//讀正確成語
for (i=0;i<m;i++)
{
scanf("%s",idiomBuffer);
pIdiom[i]=new char[9];
memcpy(pIdiom[i],idiomBuffer,9);
}
//讀待糾錯(cuò)成語
scanf("%s",wrongString);
//--------讀取數(shù)據(jù)完畢-------------
//把帶糾錯(cuò)成語對(duì)應(yīng)的正確成語找出來
int diffcount=0;//每個(gè)成語中不同的漢字個(gè)數(shù)
int count=0;//計(jì)數(shù)
for (i=0;i<m;i++)
{
diffcount=0;
for (j=0;j<4;j++)
{
if (diffcount>=2)
{
break;
}
else
{
if(pIdiom[i][2*j]!=wrongString[2*j] || pIdiom[i][2*j+1]!=wrongString[2*j+1])
{
//不同的漢字
diffcount++;
}
}
}
if (diffcount==1)//只有一個(gè)字不同的成語找出來
{
pSet[count]=new char[9];
memcpy(pSet[count],pIdiom[i],9);
count++;
}
}
//找出待糾錯(cuò)成語中錯(cuò)的那個(gè)字
char wrongChar[2];//放錯(cuò)字
int charIndex(0);//錯(cuò)字的索引
for (i=0;i<4;i++)
{
if (!(wrongString[2*i]==pSet[0][2*i] && wrongString[2*i+1]==pSet[0][2*i+1]))
{
charIndex = i;
wrongChar[0]=wrongString[2*i];
wrongChar[1]=wrongString[2*i+1];
break;
}
}
//找到錯(cuò)字所屬的漢子類別
int classIndex(0);//存放正確汗字類的索引
bool find=false;//找到這個(gè)錯(cuò)字
for (i=0;i<n;i++)
{
tempLen[i] = tempLen[i]>>1;//右移除以2
for (j=0;j<tempLen[i];j++)
{
if (wrongChar[0]==pClass[i][2*j] && wrongChar[1]==pClass[i][2*j+1])
{
classIndex = i;
find = true;
break;
}
}
if (find)
{
break;
}
}
//找到可糾正位置的漢字和錯(cuò)字所屬類相同的正確成語，輸出
for (i=0;i<count;i++)
{
for (j=0;j<tempLen[classIndex];j++)
{
if (pSet[i][2*charIndex]==pClass[classIndex][2*j] && pSet[i][2*charIndex+1]==pClass[classIndex][2*j+1])
{
printf("%s",pSet[i]);//輸出正確成語
break;
}
}
}
return 0;
}
文章出處：http://www.diybl.com/course/3_program/c++/cppsl/200863/120780.html