本文代碼皆是可運(yùn)行代碼，選用了邏輯和實(shí)現(xiàn)最簡單的方式呈現(xiàn)，部分代碼帶有注解，可供初學(xué)者學(xué)習(xí)！【點(diǎn)贊+收藏】
目錄
一、三指針：
二、漢諾塔：
三、N皇后問題：
四、熄燈問題：
五、二進(jìn)制密碼鎖
六、快排（模板）
七、歸并排序（模板）
八、逆序?qū)Φ臄?shù)量：
九、遞歸求波蘭表達(dá)式：
十、2的冪次方表示：
十一、海拉魯城堡：?
十二、真假記憶碎片：
十三、算24：
十四、騎士林克的憐憫
十五、擊殺黃金蛋糕人馬：
十六、撥鐘問題：
十七、英杰們的蛋糕塔：
十八、尋找林克的回憶（1）：
十九、尋找林克的回憶（2）：
二十、尋找林克的回憶（3）：
二十一、凈化迷霧森林：
二十二、加農(nóng)的入侵：
二十三、假幣問題：
二十四、滾石柱：
二十五、算法學(xué)習(xí)心得：
一、三指針：
三指針的關(guān)鍵是將復(fù)雜度從O（）降到O（），如何做到呢？
比如一般的思路就是用下面的三重for循環(huán)來逐個(gè)比對值，看看三數(shù)和會(huì)不會(huì)等于target，但這樣的話時(shí)間復(fù)雜度就是。
for(int i=0;i<pos;i++)
for(int j=i+1;j<pos;j++)
for(int k=j+1;k<pos;k++)
{
if(v[i]+v[j]+v[k]==target){
cout << v[i] << ' ' << v[j] << ' ' << v[k] << endl;
}
}下面的程序是優(yōu)化后的，令i和j的功能不變，唯一改變的是k，k指向數(shù)組的末尾，且要保證j<k，此時(shí)循環(huán)內(nèi)部用一個(gè)while循環(huán)，相當(dāng)于固定了i和j只去移動(dòng)k，因?yàn)閿?shù)組是經(jīng)過排序的（從小到大），如果移動(dòng)k的過程中，三數(shù)之和大于了target，k就要往前移動(dòng)1位，k--。終止的條件就是三數(shù)之和等于或小于k，如果是等于那么下面的if語句就會(huì)將其輸出，如果是小于則略過if語句，j++進(jìn)入下一次循環(huán)。
for(int i=0;i<pos;i++)
for(int j=i+1,k=pos;j<k;j++)
{
while(j<k && v[i]+v[j]+v[k]>target) k--;
if(v[i]+v[j]+v[k]==target)
{
cout << v[i] << ' ' << v[j] << ' ' << v[k] << endl;
}
}因此三指針可以理解為，固定其中兩個(gè)指針，然后去移動(dòng)另一個(gè)指針，從而將復(fù)雜度控制在平方級別。下面是程序：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v;
int target,n,pos;
void f(int pos)
{
for(int i=0;i<pos;i++)
for(int j=i+1,k=pos;j<k;j++)
{
while(j<k && v[i]+v[j]+v[k]>target) k--;
if(v[i]+v[j]+v[k]==target)
{
cout << v[i] << ' ' << v[j] << ' ' << v[k] << endl;
}
}
}
int main()
{
cin >> target >> n;
for(int i=0;i<n;i++)
{
int m ;
cin >> m;
v.push_back(m);
sort(v.begin(),v.end());
}
for(int i=0;i<v.size();i++)
{
if(v[i]>target) pos=i-1;
}
f(pos);
} 二、漢諾塔：
幫大家簡單回顧一下漢諾塔是什么意思：漢諾塔說的是從前有三根桿，有n個(gè)圓盤，要將圓盤統(tǒng)統(tǒng)從第1根桿轉(zhuǎn)移到第3根桿上。
這看似簡單的問題，難點(diǎn)有2：
第1個(gè)難點(diǎn)：規(guī)定了第1根桿上的圓盤是從下到上，從大到小堆疊的，也就是說——最下面的盤子是最大的。轉(zhuǎn)移到第3根桿上的時(shí)候，最下面的盤子也要是最大的。因?yàn)橹荒軓淖钌戏街饌€(gè)取盤子，所以我們不能直接把盤子直接從第1根桿上直接轉(zhuǎn)移到第3根桿上，那樣最下方的盤子是最小的，不符合要求。
第2個(gè)難點(diǎn)：在轉(zhuǎn)移的過程中，不能讓上方的盤子大于下方的盤子。意思就是在轉(zhuǎn)移的過程中，盤子的狀態(tài)也必須是從下到上，從大到小。
所以我們分析一下這個(gè)問題：能不能通過另外一根桿子，先將第1根桿上的，除了最后的一個(gè)盤子，先轉(zhuǎn)移到第2根桿上。然后再把第1根桿上剩下的那個(gè)大盤子轉(zhuǎn)移到第3根桿上。再把第2根桿上的盤子按照這種操作全部轉(zhuǎn)移到第3根桿上。
然而事情還遠(yuǎn)沒有這么簡單。首先，若想把第1根桿上的，除了最后的一個(gè)盤子，轉(zhuǎn)移到第2根桿上，我們必須借助第3根桿，
怎么樣？是不是感覺有點(diǎn)清晰了，這樣“重復(fù)的操作”就是我們所稱的遞歸。
而所謂的遞歸，通俗一點(diǎn)來說：就是執(zhí)行重復(fù)的一段操作，只是數(shù)量的規(guī)模更小。就像上面的1和2，執(zhí)行的操作都是一樣的，就像抽絲剝繭一樣，一層層直達(dá)內(nèi)核，而這個(gè)內(nèi)核就是我們所說的退出條件。
那這道題的退出條件是什么呢？
就是等到第1根桿上只剩下最后1個(gè)盤子的時(shí)候，直接將其轉(zhuǎn)移到第3根桿上就可以啦。
接下來我將詳細(xì)講解一下算法，保證通俗易懂：
第1步：我們先定義一個(gè)“轉(zhuǎn)移”函數(shù)，目的就是模擬盤子轉(zhuǎn)移的過程。代碼如下，將盤子從x轉(zhuǎn)移到y(tǒng)，x和y分別代表的是桿子的代號，比如A，B：
void move(char x,char y)
{
printf("%c->%c",x,y);
}第2步：寫遞歸函數(shù)和退出條件。先解釋一下各參數(shù)的含義：n代表盤子數(shù)，start、end分別代表盤子轉(zhuǎn)移過程的起點(diǎn)和終點(diǎn)。temp代表中間用于臨時(shí)放置盤子的桿子。
當(dāng)n等于1時(shí)，表明只剩下最后一個(gè)盤子，直接調(diào)用move函數(shù)，將盤子從第1根桿轉(zhuǎn)移到第3根桿，然后退出。
void f(int n,char start,char temp,char end)
{
if(n==1)
{
move(start,end);
return ;
}
}第3步：編寫main函數(shù)，n表示盤子數(shù)，A,B,C分別代表3根桿子，A桿是起始桿，C桿是目標(biāo)桿，B桿是調(diào)整桿：
int main()
{
int n;
cin >> n;
f(n,A,B,C);
return 0;
}以上就是初始的準(zhǔn)備工作，接下來開始講解如何具體編寫遞歸函數(shù)主體：
首先我們明確的一下步驟：
第1步：將第1根桿（start）上的，除最后一個(gè)盤，移動(dòng)到第2根桿（temp）上。
f(n-1,start,end,temp);可能看到這段代碼會(huì)有一些困惑，因?yàn)槲覀兊膮?shù)列表是如下圖：
void f(int n,char start,char temp,char end)大家可以這么理解：除去int n這個(gè)參數(shù)之后的第一個(gè)參數(shù)位置（start）就是第1根桿 起始桿，第二個(gè)參數(shù)位置（temp）就是第2根桿 調(diào)整桿，第三個(gè)參數(shù)位置（end）就是第3根桿 目標(biāo)桿。
盤子傳遞的過程就是從第1根桿到第3根桿的過程，所以我們只需要改變start和end的傳入?yún)?shù)，就可以模擬實(shí)現(xiàn)這個(gè)過程。
因此我們才將start放在第1個(gè)位置，temp放在第3個(gè)位置，目的就是為了讓第1根桿上的盤轉(zhuǎn)移到第2根桿上。
還可以這么理解：第1個(gè)參數(shù)位置就是盤子要轉(zhuǎn)移的起始位置，第3個(gè)參數(shù)位置就是盤子要轉(zhuǎn)移的終止位置。
第2步：將第1根桿上的剩下那個(gè)盤轉(zhuǎn)移到第3根桿上：
move(start,end);因?yàn)閟tart是第1根起始桿嘛，end是第3根目標(biāo)桿嘛，這點(diǎn)比較好理解。
第3步：將第2根桿上的所有盤子（n-1個(gè)）重復(fù)上述的步驟，全部移動(dòng)到第3根桿子上。
f(n-1,temp,start,end) ;這一步就比較跳躍了，除去n-1這個(gè)參數(shù)后，第一個(gè)參數(shù)傳入temp代表第2根調(diào)整桿上的盤子，第三個(gè)參數(shù)傳入end代表第3根目標(biāo)桿。相當(dāng)于就是把調(diào)整桿上的盤子全部按照上述的步驟轉(zhuǎn)移到目標(biāo)桿上。
下面就是遞歸每一步的
void f(int n,char start,char temp,char end)
//參數(shù)：n=3,start=A,temp=B,end=C
f(n-1,start,end,temp);
//參數(shù)：n=2,start=A,temp=C,end=B
f(n-1,start,end,temp);
//參數(shù)：n=1,start=A,temp=B,end=C
if(n==1) {move(start,end);return ;} //輸出：A->C
//參數(shù)：n=2,start=A,temp=C,end=B 【回退】
move(start,end); //輸出：A->B
//參數(shù)：n=2,start=A,temp=C,end=B
f(n-1,temp,start,end) ;
//參數(shù)：n=1,start=C,temp=A,end=B
if(n==1) {move(start,end);return ;} //輸出：C->B
//參數(shù)：n=3,start=A,temp=B,end=C 【回退】
move(start,end); //輸出:A->C
//參數(shù)：n=3,start=A,temp=B,end=C
f(n-1,temp,start,end);
//參數(shù)：n=2,start=B,temp=A,end=C
f(n-1,start,end,temp);
//參數(shù)：n=1,start=B,temp=C,end=A
if(n==1) {move(start,end);return ;} //輸出：B->A
//參數(shù)：n=2,start=B,temp=A,end=C 【回退】
move(start,end); //輸出：B->C
//參數(shù)：n=2,start=B,temp=A,end=C
f(n-1,temp,start,end) ;
//參數(shù)：n=1,start=A,temp=B,end=C
if(n==1) {move(start,end);return ;} //輸出：A->C
三、N皇后問題：
#include <iostream>
using namespace std;
const int N = 20;
// bool數(shù)組用來判斷搜索的下一個(gè)位置是否可行
// col列，dg對角線，udg反對角線
// g[N][N]用來存路徑
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u) {
// u == n 表示已經(jīng)搜了n行，故輸出這條路徑
if (u == n) {
for (int i = 0; i < n; i++) puts(g[i]); // 等價(jià)于cout << g[i] << endl;
puts(""); // 換行
return;
}
// 枚舉u這一行，搜索合法的列
int x = u;
for (int y = 0; y < n; y++)
// 剪枝(對于不滿足要求的點(diǎn)，不再繼續(xù)往下搜索)
if (col[y] == false && dg[y - x + n] == false && udg[y + x] == false) {//x代表行，y代表列
col[y] = dg[y - x + n] = udg[y + x] = true;
g[x][y] = 'Q';
dfs(x + 1);
g[x][y] = '.'; // 恢復(fù)現(xiàn)場
col[y] = dg[y - x + n] = udg[y + x] = false;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
g[i][j] = '.';
dfs(0);
return 0;
}
四、熄燈問題：
這題原本想用bitset來做，但發(fā)現(xiàn)bitset無法測量讀入二進(jìn)制數(shù)的實(shí)際長度，因此只能用string來做
#include <bitset>
#include <cstring>
#include <iostream>
#include <memory>
using namespace std;
bitset<6> source[6],//初始化輸入的燈矩陣，一個(gè)比特表示一盞燈 6行6列
light[5], //不停變化的燈矩陣 5行6列
res[5],//結(jié)果燈矩陣 5行6列
line; //某一行的開關(guān)狀態(tài)，注意是開關(guān)狀態(tài)而不是燈的狀態(tài)
void Output(int t) //輸出函數(shù)用于輸出
{
cout << "PUZZLE #" << t << endl;
for (int i=0;i<5;i++)
{
for(int j=0;j<6;j++)
{
cout << res[i][j] << ' ';
}
cout << endl;
}
}
int main(){
int T; //輸入用例個(gè)數(shù)
cin >> T;
for (int t=1;t<=T;t++) //對每個(gè)用例處理
{
//初始化燈矩陣
for(int i=0;i<5;i++)
for(int j=0;j<6;j++)
{
int x;
cin >> x;
source[i].set(j,x); //對第i行j列賦值x
}
//第1行的6個(gè)按鈕開關(guān)排列的64種情況，對每種情況單獨(dú)處理
for(int n=0;n<64;++n)
{
for(int i=0;i<5;i++) light[i]=source[i]; //將source初始數(shù)據(jù)全部復(fù)制到light中
line =n ; //將line表示成開關(guān)情況
for(int i=0;i<5;i++)
{
res[i]=line; //將line的結(jié)果賦值到res數(shù)組中
for(int j=0;j<6;++j)
{
if(line.test(j)) //對每列逐位列舉，看是否是1，若是1代表會(huì)按下該開關(guān)
{
if(j>0) light[i].flip(j-1); //該位左側(cè)改變
light[i].flip(j); //該位改變
if(j<5) light[i].flip(j+1); //該位右側(cè)改變
}
}
if(i<4) light[i+1] ^= line; //下一行的數(shù)據(jù)與當(dāng)前的數(shù)據(jù)進(jìn)行異或，更新當(dāng)前行按鈕按下后，下一行的狀態(tài)
line=light[i]; //更新line的值
}
if(light[4].none())//如果第4行的燈全部熄滅
{
Output(t);//輸出
break;
}
}
}
return 0;
} 五、二進(jìn)制密碼鎖
這道題要注意兩個(gè)點(diǎn)：第一點(diǎn)：第1個(gè)按鈕是否按下，第1個(gè)按鈕的情況會(huì)決定后面所有按鈕。第二點(diǎn)：一定是按下不同位的下一個(gè)按鈕。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
void flip(string & str,int i) { //用于取反某一位
if(str[i]=='1') str[i]='0';
else if(str[i]=='0') str[i]='1';
}
int main()
{
string line;
string lock;
int mint=10000;
cin >> line;
string startlock = line;
cin >> line;
string targetlock=line;
int n = line.size();
for(int p=0;p<=1;++p) //分2種情況，用于確定第1位是否要按下
//所以第1位的情況會(huì)決定后面所有的情況
{
lock = startlock;
int t=0; //t用于統(tǒng)計(jì)個(gè)數(shù)
int next = p;
for(int i=0;i<n;i++)
{
if(next==1){
if(i>0) flip(lock,i-1);
flip(lock,i);
if(i<n-1) flip(lock,i+1);
++t;
}
if(lock[i]!=targetlock[i]) next=1; //用于保證延后一位進(jìn)行取反
else next=0;
}
if(lock==targetlock) mint=min(t,mint);
}
if(mint==10000) cout << "impossible";
else cout << mint;
return 0;
}六、快排（模板）
#include <iostream>
using namespace std;
int nums[100000];
void f(int left,int right)
{
int l=left-1,r=right+1,mid=nums[(left+right)/2];
if(left>=right) return;
while(l<r)
{
do {l++;} while(nums[l]<mid);
do {r--;} while(nums[r]>mid);
if(l<r) swap(nums[l],nums[r]);
}
f(left,r);
f(r+1,right);
}
int main()
{
int n;
cin >> n;
int k;
cin >> k;
for(int i=0;i<n;i++)
cin >> nums[i];
f(0,n-1);
cout << nums[k-1]<<endl;
}七、歸并排序（模板）
第1步：設(shè)置結(jié)束條件，左邊大于或等于右邊
第2步：設(shè)置中點(diǎn)，設(shè)置指針指向兩段的最左側(cè)
第3步：對兩段分別進(jìn)行遞歸
第4步：準(zhǔn)備一個(gè)臨時(shí)數(shù)組，將較小的數(shù)存放進(jìn)入
第5步：進(jìn)行收尾
第6步：將新的數(shù)組逐一賦值給舊的數(shù)組
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int nums[100000];
int temp[100000];
void mergeSort(int left,int right)
{
if(left>=right) return ;
int mid = (left+right)>>1;
int l=left,r=mid+1,k=0;
mergeSort(left,mid);
mergeSort(mid+1,right);
while(l<=mid && r<=right){
if(nums[l]<nums[r]) temp[k++]=nums[l++];
else temp[k++]=nums[r++];
}
while(l<=mid) temp[k++]=nums[l++];
while(r<=right) temp[k++]=nums[r++];
for(int i=left,k=0;i<=right;i++,k++) nums[i]=temp[k];
}
int main()
{
int n;
cin >> n;
for(int i=0;i<n;i++) cin >> nums[i];
mergeSort(0,n-1);
for(int i=0;i<n;i++) cout << nums[i] << ' ';
}八、逆序?qū)Φ臄?shù)量：
用的是歸并排序。
注意返回值是LL型，不然會(huì)報(bào)錯(cuò)
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 100007;
int n;
int numbers[N],tmp[N];
LL mergeSort(int nums[],int left,int right) //注意返回值是LL型
{
if(left >= right) return 0;
int mid = left+right >> 1;
LL result = mergeSort(nums,left,mid)+mergeSort(nums,mid+1,right);
int k=0,p=left,q=mid+1;
//下面是對排序完結(jié)果合并
while(p<=mid && q<=right) if(nums[p]<=nums[q]) tmp[k++] = nums[p++];
else{//nums[p]>nums[q]滿足逆序?qū)Φ臈l件
//因?yàn)槭菑男〉酱笈判颍詐后面的數(shù)都比nums[p]大，所以p后面的數(shù)都能和nums[q]進(jìn)行結(jié)合生成逆序?qū)? result += mid - p +1; //為什么是mid-(p-1)因?yàn)檫€要算上p自身
//比如一共有5個(gè)數(shù)，下標(biāo)從0到4，中間mid是下標(biāo)2，假如下標(biāo)0的數(shù)大于nums[q]，那么reult要加幾個(gè)數(shù)呢？答案是3個(gè)：下標(biāo)0,1,2的數(shù)，包含Mid
tmp[k++]=nums[q++];
}
//下面是收尾
while(p<=mid) tmp[k++]=nums[p++];
while(q<=right)tmp[k++]=nums[q++];
//下面是賦值回原數(shù)組
for(int i=left,k=0;i<=right;i++,k++) nums[i]=tmp[k];
return result;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&numbers[i]);
cout << mergeSort(numbers,0,n-1) << endl;
return 0;
}九、遞歸求波蘭表達(dá)式：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
double f(){
string str;
cin >> str;
switch(str[0])
{
case '*' : return f()*f();break;
case '+' : return f()+f();break;
case '-' : return f()-f();break;
case '/' : return f()/f();break;
default : return(stof(str));
}
}
int main()
{
printf("%.6lf",f());
}
#測試用例：* + 11.0 12.0 + 24.0 35.0
#輸出用例：1357.000000下圖是示意圖。cin的特性是：讀入的數(shù)據(jù)以空格為分隔，一次只能讀入（兩個(gè)空格之間的）一個(gè)數(shù)據(jù)。如果讀入的是運(yùn)算符，就遞歸求得運(yùn)算符左右兩邊的值。如果讀入的是數(shù)值，就返回轉(zhuǎn)化為浮點(diǎn)數(shù)后的值，進(jìn)行運(yùn)算。只有當(dāng)一個(gè)運(yùn)算符左右兩邊的遞歸運(yùn)算結(jié)束（均返回值），才會(huì)結(jié)束該層的遞歸，其值作為上一層遞歸的運(yùn)算參數(shù)值。
十、2的冪次方表示：
#include <iostream>
#include <bitset>
using namespace std;
int getlen(int i) //計(jì)算n的二進(jìn)制數(shù)長度
{
int len=0;
while(i) //i>0就不停循環(huán)，直到為0退出
{
i >>= 1;
++len;
}
return len;
}
void convert(int num,int k)
{
if(k==0) return;
int num_k = (num >> (k-1)) &1; //從最高位開始測試,獲取最高位的二進(jìn)制值
if(!num_k) convert(num,k-1); //如果num_k等于0,就k-1,獲取次高位的二進(jìn)制以此類推。
else //如果num_k等于1則進(jìn)行處理
{
if(k!=getlen(num)) cout << "+";
if(k==1) cout << "2(0)"; //說明指數(shù)僅剩1位，是2^0=1
else if(k==2) cout <<"2";//說明指數(shù)剩2位，是2^1=2
else
{
cout << "2(";
convert(k-1,getlen(k-1));
cout << ")";
}
convert(num,k-1);
}
}
int main()
{
int n;
cin >> n;
convert(n,getlen(n));
return 0;
} 十一、海拉魯城堡：?
#include <iostream>
using namespace std;
const int N = 55;
int m,n,cntroom,roomarea,maxarea;
int room[N][N];
bool st[N][N];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
//(0,-1)往左，(-1,0)往上，(0,1) 往右，(1,0)往下
void dfs(int x,int y)
{
st[x][y]=true;
++ roomarea;
for(int i=0;i<4;++i){
int nx=dx[i]+x,ny=dy[i]+y;
if(nx<0 || ny<0 || nx>=m || ny>=n )continue;
if(st[nx][ny]) continue;
if(room[x][y]>>i&1)continue; //注意是對當(dāng)前所站的格子來判斷朝向是否有墻，后面才能遞歸朝該方向行走，這一點(diǎn)千萬要注意。
dfs(nx,ny);
}
}
int main()
{
cin >> m >> n;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
cin >> room[i][j];
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++)
{
if(!st[i][j]){
++cntroom;roomarea=0;
dfs(i,j);
maxarea = max(maxarea,roomarea);
}
}
}
cout << cntroom <<endl;
cout << maxarea;
}十二、真假記憶碎片：
#include <iostream>
#include <cstring>
using namespace std;
const int N =9;
const int M=3;
int a[N][N],b[N][N];
bool st[N+1];
string memory[N]={{"530070000"},{"600195000"},{"098000060"},{"800060003"},{"400803001"},{"700020006"},{"060000280"},{"000419005"},{"000080079"}};
const int n = 9;
bool check_input(){
string line;
for(int i=0;i<N;i++)
{
cin >> line;
if(line.size()!=N) return false; //長度不對
for(int j=0;j<N;j++) {
int t = line[j]-'0'; //字符轉(zhuǎn)整數(shù)
if(t<1 || t>N) { //出現(xiàn)不是1到9的數(shù)字
return false;
}
if(a[i][j]!=0 && a[i][j]!=t) return false; //輸入的值與初始值不匹配
b[i][j]=t;
}
}
return true;
}
bool check_row(){
for(int i=0;i<N;i++){
memset(st,false,sizeof(st));
for(int j=0;j<N;j++)
{
int t = b[i][j];
if(t<0 || t>N) return false;
if(st[t]) return false;
st[t]=true;
}
}
return true;
}
bool check_col()
{
for(int i=0;i<N;i++){
memset(st,false,sizeof(st));
for(int j=0;j<N;j++)
{
int t=b[j][i];
if(t<0 || t>N) return false;
if(st[t]) return false;
st[t]=true;
}
}
return true;
}
bool check_block(){
for(int x=0;x<N;x += M)
for(int y=0;y<N; y += M)
{
memset(st,false,sizeof(st));
for(int dx=0;dx<M;dx++)
for(int dy=0;dy<M;dy++)
{
int t = b[x+dx][y+dy];
if(t<0 || t>N) return false;
if(st[t]) return false;
st[t]=true;
}
}
return true;
}
int main()
{
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
a[i][j]=memory[i][j]-'0';
}
if(check_input() && check_row() && check_col() && check_block())
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}十三、算24：
#include<iostream>
#include<cmath>
#define efs 1e-6 //PS1：注意efs的定義方式
using namespace std;
bool f(double n);
bool count24(double a[], int n);
int main()
{
double arr[5] = { 0 };
while (cin >> arr[0] >> arr[1] >> arr[2] >> arr[3] && arr[0] + arr[1] + arr[2] + arr[3] > 0)
{
if (count24(arr, 4))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
bool f(double n) //PS2:注意浮點(diǎn)數(shù)一定要用小于很小數(shù)的方式來判斷是否等于0
{
if (fabs(n) < efs) //PS3:注意要對n取絕對值！！
return true;
else return false;
}
bool count24(double a[], int n)
{
if (n == 1)
{
if (f(a[0] - 24)) //PS4:4數(shù)作運(yùn)算的結(jié)果存在a[0]中
return true;
return false;
}
double b[5] = { 0 }; //PS5:定義的數(shù)組b專門用于存放n-1個(gè)數(shù)
//選擇任意不同的兩個(gè)數(shù)進(jìn)行運(yùn)算
for (int i = 0; i < n ; ++i) //PS6:千萬千萬注意，n的值是會(huì)變的而不是一直是4，會(huì)從4,3,2遞減
{
for (int j = 0; j < n; ++j)
{
if (i == j)continue; //PS7:跳過取值相同的數(shù)
int m = 0;
for (int k = 0; k < n; ++k) //PS8:k是未被取到的剩余數(shù)的下標(biāo)
{
if (k != i && k != j)
b[m++] = a[k]; //把其余的數(shù)放到數(shù)組里
}
//把運(yùn)算后的數(shù)放到數(shù)組里
//下面可以視為是對4中情況，加減乘除分別作為一種情況進(jìn)行遞歸
b[m] = a[i] + a[j];
if (count24(b, n - 1))//對運(yùn)算后的n-1個(gè)數(shù)進(jìn)行算24操作
return true;
b[m] = a[i] - a[j];
if (count24(b, n - 1))
return true;
b[m] = a[i] * a[j];
if (count24(b, n - 1))
return true;
if (a[j] != 0)b[m] = a[i] / a[j];
if (count24(b, n - 1))
return true;
}
}
return false; //PS9:如果途中沒有返回true最后要返回false
}十四、騎士林克的憐憫
第1點(diǎn)：千萬千萬注意：這道題的X軸式字母的那條軸，而不是一般豎直的這條軸。原因是vector<pair<char, int>> path;我們設(shè)定了pair的第一個(gè)元素是字符型，第二個(gè)元素是整型，dfs傳入的第一個(gè)參數(shù)x對應(yīng)的是第一個(gè)字符型元素，因此x軸必須是橫軸。所以一定要注意dx，dy數(shù)組值的填寫。
第2點(diǎn)：這題還有一個(gè)陷阱，就是要輸出字典序最小的路線，所謂字典序最小，就是從第1個(gè)字符到最后一個(gè)字符，與其它字符相比，都必須要是最小的序列，所以：for (int i = 0; i < q; i++）for (int j = 0; j < p; j++)就是將i視為橫軸，將j視為縱軸，a[i][j]就是按照豎直方向進(jìn)行搜索，A1比A2小比B1小，因?yàn)锳的ascii碼為97，1的ascii碼為49。
#include <utility>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
const int N = 27;
int p, q;
bool st[N][N];
vector<pair<char, int>> path;
int dx[8] = { -2,-2,-1,-1,1,1,2,2 };
int dy[8] = { -1,1,-2,2,-2,2,-1,1 };
bool dfs(int x, int y, int cnt)
{
path.push_back({ char(x + 'A'),y + 1 });
if (cnt == p * q) {
for (auto a : path) cout << a.first << a.second;
return true;
}
st[x][y] = true;
for (int i = 0; i < 8; i++)
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= q || b < 0 || b >= p) continue;
if (st[a][b]) continue;
if (dfs(a, b, cnt + 1)) return true; //這點(diǎn)很重要，能保證輸出的是字典序最小的。
}
st[x][y] = false;
path.pop_back();
return false;
}
int main()
{
int T;
cin >> T;
for (int t = 1; t <= T; t++)
{
cout << "#" << t << ":" << endl;
cin >> p >> q;
path.clear();
memset(st, 0, sizeof(st));
bool flag = false;
for (int i = 0; i < q; i++) //i代表橫軸
for (int j = 0; j < p; j++) //j代表縱軸
//這樣操作的目的是讓字典序最小
{
if (dfs(i, j, 1)) {
flag = true;
break;
}
}
if (!flag) cout << "none";
cout << endl;
}
}
十五、擊殺黃金蛋糕人馬：
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define _For(a,b,c) for(int a=b;a<=c;++a)
#define _RFor(a,b,c) for(int a=b;a>=c;--a)
#define Clear(a,b) memset(a,b,sizeof(a))
const int Inf=0x3f3f3f3f,Inf2=0x7fffffff;
int W,H,M; //寬，高，切成M塊
int minMax[27][27][407];
int dfs(int wide,int height,int cutNumber)
{
if(wide*height < cutNumber +1) //不夠斬
return Inf;
if(cutNumber==0) //斬完畢
return wide * height;
if(minMax[wide][height][cutNumber]!=-1)
return minMax[wide][height][cutNumber];
int minMArea = 0;
minMArea = Inf;
for(int i=1;i<=wide-1;i++)
for(int k=0;k<=cutNumber-1;k++)
{
int m1 = dfs(i,height,k);
int m2 = dfs(wide-i,height,cutNumber-1-k);
minMArea = min(minMArea,max(m1,m2));
}
for(int j=1;j<=height-1;j++)
for(int k=0;k<=cutNumber-1;k++)
{
int r1=dfs(wide,j,k);
int r2=dfs(wide,height-j,cutNumber-1-k);
minMArea= min(minMArea,max(r1,r2));
}
return minMax[wide][height][cutNumber] = minMArea;
}
int main()
{
while(true){
cin >> W >>H >>M;
if(W==0 && H==0) break;
Clear(minMax,-1);
cout << dfs(W,H,M-1) <<endl;
}
return 0;
}
十六、撥鐘問題：
思路：先遞歸給每個(gè)方案賦予一個(gè)撥動(dòng)次數(shù)（0到4），直到9個(gè)時(shí)方案都被賦予完畢。然后遍歷9種移動(dòng)方案，將每種方案中的[全部時(shí)鐘]，都撥動(dòng)當(dāng)前方案所需撥動(dòng)的次數(shù)。如果最后時(shí)鐘都指向0點(diǎn)，就輸出方案。
所以整道題的思路就是：遞歸賦予每種方案一個(gè)執(zhí)行的次數(shù)然后執(zhí)行，看執(zhí)行后的結(jié)果是否能使所有時(shí)鐘指針歸0。怎么樣，很神奇吧??！
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int oriClocks[9]; //時(shí)鐘初始狀態(tài)
int clocks[9]; //計(jì)算過程中時(shí)鐘狀態(tài)
int moveTimes[9]={0}; //9個(gè)時(shí)鐘，每個(gè)時(shí)鐘被撥動(dòng)的次數(shù)
int minTimes=1<<30; //存儲(chǔ)最少的撥動(dòng)次數(shù)
int result[9]; //存儲(chǔ)最少的撥動(dòng)方案
string moves[9]={"ABDE","ABC","BCEF","ADG","BDEFH","CFI","DEGH","GHI","EFHI"};
void dfs(int n) //當(dāng)前是第n號方案
{
if(n>=9) //每個(gè)方案都有撥動(dòng)次數(shù)
{
memcpy(clocks,oriClocks,sizeof(clocks));
int times = 0;
for(int i=0;i<9;i++){ //9種移動(dòng)方案
if(moveTimes[i]){ //該移動(dòng)方案執(zhí)行moveTimes[i]次
//下面是改變時(shí)鐘指向操作
for(int k=0;k<moves[i].size();k++)
{
// moves[i][k]-'A'獲取的是時(shí)鐘號，clocks[moves[i][k]-'A']代表的就是當(dāng)前時(shí)鐘的狀態(tài)
clocks[moves[i][k]-'A'] = (clocks[moves[i][k]-'A']+moveTimes[i])%4;//更新時(shí)鐘指向
times += moveTimes[i]; //統(tǒng)計(jì)撥動(dòng)的次數(shù)
}
}
}
//下面是判斷是否成功，9個(gè)鐘都指向0點(diǎn)
bool flag = true;
for(int i=0;i<9;i++) //遍歷9個(gè)時(shí)鐘
if(clocks[i]!=0){ //只要有一個(gè)鬧鐘不是指向0點(diǎn)
flag = false; //不成功
break;
}
//下面是成功情況
if(flag && minTimes > times){ //最小撥動(dòng)次數(shù)大于當(dāng)前次數(shù)要更新
minTimes = min(minTimes,times);
memcpy(result,moveTimes,sizeof(result)); //這部關(guān)鍵，將最少移動(dòng)序列拷貝到結(jié)果
}
return;
}
for(int i=0;i<4;i++) //最多4次一定恢復(fù)到0點(diǎn)
{
moveTimes[n]=i; //給每個(gè)方案賦予一個(gè)執(zhí)行的次數(shù)
dfs(n+1); //遞歸下一個(gè)方案
}
return ;
}
int main(){
for(int i=0;i<9;i++) cin >> oriClocks[i];
dfs(0);
for(int i=0;i<9;i++)//第1重循環(huán)用于遍歷9種方案，
for(int k=0;k<result[i];k++) //result[i]存儲(chǔ)的是每個(gè)方案需要執(zhí)行的次數(shù)
//必須用這種形式輸出，因?yàn)槟承┓桨缚赡軋?zhí)行不止一次??！
cout << i+1 <<" "; //輸出方案
}
十八、尋找林克的回憶（1）：
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 9;
int g[N][N];
bool st_row[N][N + 1], st_col[N][N + 1], st_block[3][3][N + 1];
bool dfs(int x, int y) {
if (y == 9) x++, y = 0;
if (x == 9) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) cout << g[i][j];
cout << endl;
}
return true;
}
if (g[x][y] != 0) return dfs(x, y + 1); //這段是關(guān)鍵，一定要是return
for (int t = 1; t <= 9; t++) {
if (!st_row[x][t] && !st_col[y][t] && !st_block[x / 3][y / 3][t]) //注意x和y都要/3
{
st_row[x][t] = st_col[y][t] = st_block[x / 3][y / 3][t] = true;
g[x][y] = t;
if (dfs(x, y + 1)) return true;
g[x][y] = 0;
st_row[x][t] = st_col[y][t] = st_block[x / 3][y / 3][t] = false;
}
}
return false;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(NULL), std::cout.tie(NULL);
memset(st_row, 0, sizeof(st_row));
memset(st_col, 0, sizeof(st_col));
memset(st_block, 0, sizeof(st_block));
for(int i=0;i<9;i++)
for (int j = 0; j < 9; j++)
{
char ch;
cin >> ch;
int t = ch - '0';
g[i][j] = t;
if (t != 0)
st_row[i][t] = st_col[j][t] = st_block[i / 3][j / 3][t] = true;
}
dfs(0, 0);
return 0;
}十九、尋找林克的回憶（2）：
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 9;
int ones[1 << N], LOG[1 << N];
int row[N], col[N], block[3][3];
string str;
inline int lowbit(int x)
{
return x & -x;
}
void init()
{
//1<<N，其中N為10，相當(dāng)于將1左移10位，十進(jìn)制值為1024，減去1值為1023
//1023的二進(jìn)制值為111111111，一共9個(gè)1，所以row和col的一個(gè)位便相當(dāng)于存儲(chǔ)了9個(gè)1
//初始化為全1，如果有該數(shù)則減掉該數(shù)
for (int i = 0; i < N; i++) row[i] = col[i] = (1 << N) - 1;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
block[i][j] = (1 << N) - 1;
}
inline int get(int x, int y)
{
//注意一個(gè)&符號是作與運(yùn)算，看看三個(gè)對應(yīng)位上是否都是1，如果是就說明這個(gè)數(shù)的下標(biāo)沒有出現(xiàn)過
return row[x] & col[y] & block[x / 3][y / 3];
}
bool dfs(int cnt)
{
if (!cnt) return true; //待填空的位置個(gè)數(shù)為0
int minv = 10;
int x, y;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if (str[i * 9 + j] == '.') //是.說明需要填寫
{
int t = ones[get(i, j)]; //get(i,j)返回的是一個(gè)十進(jìn)制數(shù)
//而ones數(shù)組可以返回十進(jìn)制數(shù)中1的個(gè)數(shù)，將數(shù)賦值給t
if (t < minv) //目的是要獲取可填數(shù)最少的位置
//從可填數(shù)最少的位置一直到可填數(shù)最多的位置，這樣dfs的入口會(huì)小，最后的情況數(shù)就會(huì)少
{
minv = t;
x = i;
y = j;
}
}
for (int i = get(x, y); i; i -= lowbit(i))
{
int t = LOG[lowbit(i)]; //LOG數(shù)組可以獲取lowbit所返回?cái)?shù)的1的位置
row[x] -= 1 << t; //相當(dāng)于把第t位的1進(jìn)行移除
col[y] -= 1 << t;
block[x / 3][y / 3] -= 1 << t;
str[x * 9 + y] = '1' + t;
if (dfs(cnt - 1)) return true;
row[x] += 1 << t; //進(jìn)行回溯反向操作
col[y] += 1 << t;
block[x / 3][y / 3] += 1 << t;
str[x * 9 + y] = '.';
}
return false;
}
int main()
{
for (int i = 0; i < N; i++) LOG[1 << i] = i;
for (int i = 0; i < 1 << N; i++)
{
int s = 0;
for (int j = i; j; j -= lowbit(j)) s++;
ones[i] = s; //ones數(shù)組用于記錄某個(gè)數(shù)會(huì)有幾個(gè)1
}
while (cin >> str, str[0] != 'e')
{
init();
int cnt = 0;
for (int i = 0, k = 0; i < N; i++)
for (int j = 0; j < N; j++, k++) //這個(gè)地方k的值很巧妙
//第1輪k從0到8，第2輪從9到17，因?yàn)闆]設(shè)定k結(jié)束值，所以每次都會(huì)隨i值的變化繼續(xù)累加
if (str[k] != '.')
{
int t = str[k] - '1'; //注意這里是減去字符1
//假如值是3，就要把1左移2位，得到100，因此是用3-1得到t的值為2
row[i] -= 1 << t;
col[j] -= 1 << t;
block[i / 3][j / 3] -= 1 << t;
}
else cnt++; //cnt表示的待填空的位置個(gè)數(shù)
dfs(cnt);
cout << str << endl;
}
return 0;
}二十、尋找林克的回憶（3）：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=9,M=1<<N;
int ones[M],LOG[M];
int row[N],col[N],block[3][3];
int g[N][N];
int ans=-1;
inline int lowbit(int x)
{
return x & -x;
}
void init()
{
for(int i=0;i<N;i++) LOG[1<<i]=i;
for(int i=0;i<M;i++)
for(int j=i;j;j-=lowbit(j))
ones[i] ++;
for(int i=0;i<9;i++) row[i]=col[i]=block[i/3][i%3]=M-1;
}
inline int get(int x,int y)
{
return row[x] & col[y] & block[x/3][y/3];
}
inline int get_score(int x,int y,int t)
{
return(min(min(x,8-x),min(y,8-y))+6)*t;
}
inline void draw(int x,int y,int t) //t傳入的是讀入的數(shù)值
//如果t為正則將row、col、block數(shù)組的那位清0
//如果t為負(fù)則將row、col、block數(shù)組的那位置1
{
int s=1;
if(t>0) g[x][y]=t;
else //t為負(fù)，相當(dāng)于是回溯的情況，看第73行前后的代碼
{
s = -1; //s取反
t = -t; //將t變?yōu)檎麛?shù)方便操作
g[x][y]=0;
}
t--; //t減1位，移位時(shí)才能移動(dòng)到正確位置
row[x] -= (1<<t) * s;
col[y] -= (1<<t) * s;
block[x/3][y/3] -= (1<<t) * s;
}
void dfs(int cnt,int score)
{
if(!cnt){
ans = max(ans,score);
return;
}
int minv = 10;
int x,y;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(!g[i][j])
{
int t = ones[get(i,j)];
if(t<minv)
{
minv = ones[get(i,j)];
x=i,y=j;
}
}
for(int i=get(x,y);i;i -= lowbit(i)) //簡化了
{
int t=LOG[lowbit(i)]+1;
draw(x,y,t);
dfs(cnt-1,score+get_score(x,y,t));
draw(x,y,-t);
}
}
int main()
{
init();
int cnt=0,score=0;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
int t;
cin >> t;
if(t)
{
draw(i,j,t);
score += get_score(i,j,t);
}
else cnt++;
}
dfs(cnt,score);
cout << ans << endl;
return 0;
}二十一、凈化迷霧森林：
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 25;
int n, m;
char g[N][N];
int bfs(int sx, int sy)
{
queue<PII> q;
q.push({ sx,sy });
g[sx][sy] = '#';
int res = 0;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
while (q.size()) {
auto t = q.front();
q.pop();
res++; //計(jì)數(shù)加在for循環(huán)外，否則會(huì)少計(jì)算初始位置
for (int i = 0; i < 4; i++) {
int x = t.first + dx[i];
int y = t.second + dy[i];
//一定要寫成g[x][y]!='.'，而且x和y必須是要大于等于，不能漏掉這個(gè)等于
if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue;
g[x][y] = '#';
q.push({ x,y });
}
}
return res;
}
int main()
{
while (cin >> m >> n, n || m)
{
for (int i = 0; i < n; i++) cin >> g[i];
int x, y;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == '@') {
x = i;
y = j;
}
cout << bfs(x, y) << endl;
}
return 0;
}二十二、加農(nóng)的入侵：
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m; //n表示行，m表示列
PII start;
char g[N][N];
int dist[N][N];
const int dx[8] = { 1,1,1,0,0,-1,-1,-1 };
const int dy[8] = { -1,0,1,-1,1,-1,0,1 };
int bfs()
{
memset(dist, -1, sizeof dist);
queue<PII> q;
q.push(start);
dist[start.first][start.second] = 0;
int res = 0;
while (q.size())
{
auto t = q.front();
q.pop();
for (int k = 0; k < 8; k++)
{
int x = t.first + dx[k];
int y = t.second + dy[k];
if (x<1 || x>n || y < 1 || y>m) continue;
if (g[x][y] == '*' || dist[x][y] != -1) continue;
dist[x][y] = dist[t.first][t.second] + 1;
res = max(res, dist[x][y]);
q.push(make_pair(x, y));
}
}
return res;
}
int main(){
cin >> m >> n >> start.second >> start.first;
start.first = n + 1 - start.first;
for (int i = 1; i <= n; i++) cin >> g[i] + 1;
cout << bfs() << endl;
return 0;
}二十三、假幣問題：
核心思想是：對所有硬幣依次假設(shè)其為假幣，再分2種情況：假幣更輕，假幣更重。因?yàn)橹挥幸幻都賻?，如果是even表示天平持平，被假定為假幣的硬幣不應(yīng)該出現(xiàn)在兩側(cè)，如果出現(xiàn)說明該硬幣不是假幣；如果是up表示右邊天平更高，如果輕的假幣不在右天平返回False，如果重的假幣不在左天平返回False;如果是down表示右天平更低，情況與up相反。
#include <iostream>
#include <queue>
typedef long long LL;
using namespace std;
const int N = 100007;
int n;
int temp[N];
int A[N];
int MergeSort(int A[], int left, int right)
{
if (left >= right) return 0;
int mid = (left + right) >> 1;
int l = left, r = mid + 1, k = 0;
LL res = MergeSort(A,l, mid) + MergeSort(A,r, right);
while (l <= mid && r <= right)
{
if (A[l] <= A[r]) temp[k++] = A[l++];
else {
temp[k++] = A[r++];
res += mid - l + 1;
}
}
while (l <= mid) temp[k++] = A[l++];
while (r <= right) temp[k++] = A[r++];
for (int i = left, k = 0; i <= right; i++, k++)
{
A[i] = temp[k];
}
return res;
}
int main()
{
scanf("%d",&n);
for (int i = 0; i < n; i++)
{
cin >> A[i];
}
cout << MergeSort(A, 0, n - 1);
return 0;
}二十四、滾石柱：
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <bitset>
using namespace std;
const int N = 507;
struct Stone //Stone的數(shù)據(jù)結(jié)構(gòu)
{
int x, y, status;
Stone(int a, int b, int c) { x = a; y = b; status = c; }
Stone() :x(0), y(0), status(0) {};
};
void displayStone(Stone& s) //測試
{
cout << "(" << s.x << " " << s.y << " " << s.status << ")";
}
//橫躺時(shí)以施主左側(cè)為基準(zhǔn)，豎躺時(shí)以石柱上側(cè)為基準(zhǔn)
int direction[4][3][3] = {
//第一個(gè)參數(shù)：上下左右滾動(dòng)
//第二個(gè)參數(shù)：不同姿勢（豎，橫塘，豎躺）滾后的狀態(tài)
//第三個(gè)參數(shù)：是橫縱坐標(biāo)和狀態(tài)
{{-2,0,2},{-1,0,1},{-1,0,0}}, //上
{{1,0,2},{1,0,1},{2,0,0}}, //下
{{0,-2,1},{0,-1,0},{0,-1,2}}, //左
{{0,1,1},{0,2,0},{0,1,2}}}; //右
Stone moveStone(Stone& p, int udlr) //返回下一個(gè)狀態(tài)坐標(biāo)
{
int dx = direction[udlr][p.status][0];
int dy = direction[udlr][p.status][1];
int newstatus = direction[udlr][p.status][2];
return Stone(p.x + dx, p.y + dy, newstatus);
}
int n, m;
char area[N][N];
int dist[N][N][3]; //標(biāo)記是否走過
queue<Stone> q;
Stone start, target, qHead;
bool isVisited(Stone node) //是否走過
{
return dist[node.x][node.y][node.status] != -1;
}
bool isInside(int x, int y) //是否在區(qū)域內(nèi)
{
return x >= 0 && x < n&& y >= 0 && y < m;
}
bool isValid(Stone node) //判斷走的是否有效
{
if (!isInside(node.x, node.y) || area[node.x][node.y] == '#') //不在區(qū)域內(nèi) || 踩到禁區(qū)
return false;
//豎躺：如果另一塊不在區(qū)域內(nèi) || 另一塊踩到禁區(qū)
if (node.status == 2 && (!isInside(node.x + 1, node.y) || area[node.x + 1][node.y] == '#'))
return false;
//橫躺：如果另一塊不在區(qū)域內(nèi) || 另一塊踩到禁區(qū)
if (node.status == 1 && (!isInside(node.x, node.y + 1) || area[node.x][node.y + 1] == '#'))
return false;
//直立：如果踩到易碎地
if (node.status == 0 && area[node.x][node.y] == 'E')
return false;
return true;
}
char readChar() //取出字符
{
char c = getchar();
while (c != '#' && c != '.' && c != 'X' && c != 'O' && c != 'E') //不在符號內(nèi)，就while跳過這些空格
c = getchar();
return c;
}
void BuildMap(int n, int m) //初始化，建立地圖
{
memset(area, '#', sizeof(area)); //初始化為禁區(qū)
memset(dist, -1, sizeof(dist)); //初始化為-1表示未讀
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
area[i][j] = readChar(); //讀入數(shù)據(jù)，建立地圖
for(int i=0;i<n;i++)
for (int j = 0; j < m; j++)
{
char c = area[i][j];
if (c == 'X') //尋找起點(diǎn)
{
start.x = i,start.y = j,start.status = 0,area[i][j] = '.'; //找到起點(diǎn)，先假設(shè)為站立，但起點(diǎn)可能不止一個(gè)，因?yàn)榭赡軝M躺也可能豎躺
if (isInside(i, j + 1) && area[i][j + 1] == 'X') //橫躺
start.status = 1, area[i][j + 1] = '.'; //更新狀態(tài)
if (isInside(i + 1, j) && area[i + 1][j] == 'X') //豎躺
start.status = 2, area[i + 1][j] = '.'; //更新狀態(tài)
}
if (c == 'O') //終點(diǎn)
target.x = i, target.y = j, target.status = 0;
}
}
int bfs(Stone& s)
{
while (q.size())
q.pop();
q.push(s);
dist[s.x][s.y][s.status] = 0;
while (q.size())
{
qHead = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
Stone next = moveStone(qHead, i);
if (!isValid(next)) continue;
if (!isVisited(next))
{
dist[next.x][next.y][next.status] = dist[qHead.x][qHead.y][qHead.status] + 1;
q.push(next);
if (next.x == target.x && next.y == target.y && next.status == target.status)
return dist[next.x][next.y][next.status];
}
}
}
return -1;
}
int main()
{
while (cin >> n >> m && n)
{
BuildMap(n, m);
int res = bfs(start);
if (res == -1)
cout << "Impossible" << endl;
else
cout << res << endl;
}
}
二十五、算法學(xué)習(xí)心得：
學(xué)習(xí)算法，最重要的是要把基礎(chǔ)先吃透，比如：vector之類的STL的基本操作要懂，引用變量的形式要懂......不然稍難一點(diǎn)的算法題解都看不懂。文章來源：http://www.zghlxwxcb.cn/news/detail-526005.html
因?yàn)樯噪y的算法題解是由一些比較進(jìn)階的用法組成的，所以在看題解的時(shí)候可以先從main函數(shù)看起，將每個(gè)部分進(jìn)行拆分，然后再逐一深入到每個(gè)函數(shù)內(nèi)部看具體的功能。先進(jìn)行拆分，逐一弄懂，再合起來進(jìn)行理解。對著程序敲一遍，然后最重要的是要自己思考動(dòng)手敲一遍。有些還是不理解的地方一定要多多注意，這些地方是值得深入進(jìn)行探究的，如果能學(xué)會(huì)這些方法，甚至可以對不同的題目進(jìn)行融會(huì)貫通。文章來源地址http://www.zghlxwxcb.cn/news/detail-526005.html
到了這里，關(guān)于C++學(xué)習(xí)算法心得和部分算法講解（三指針）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
