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