柚子快報(bào)激活碼778899分享：算法 【藍(lán)橋杯】滅鼠先鋒

http://yzkb.51969.com/

一.題目描述

?二.解題思路

博弈論：

只能轉(zhuǎn)移到必勝態(tài)的，均為必?cái)B(tài)。

可以轉(zhuǎn)移到必?cái)B(tài)的，均為必勝肽。

最優(yōu)的策略是，下一步一定是必?cái)B(tài)。

#include

#include

using namespace std;

map mp;

bool check(string s){

int cnt=0;

for(int i=0;i

if(s[i]=='o'){

cnt++;

}

}

return cnt==1;

}

bool dfs(string s){

if(mp.count(s)){

return mp[s];

}

if(check(s)){//當(dāng)前狀態(tài)只有一個(gè)o，必為必?cái)B(tài)

mp[s]=false;

return false;

}

//放置1個(gè)

for(int i=0;i

if(s[i]=='o'){

string temp=s;

temp[i]='x';

if(dfs(temp)==false){

mp[s]=true;

return true;

}

}

}

//放置2個(gè)

for(int i=0;i

if(s[i]=='o'&&s[i+1]=='o'&&i!=3){

string temp=s;

temp[i]='x';

temp[i+1]='x';

if(dfs(temp)==false){

mp[s]=true;

return true;

}

}

}

mp[s]=false;

return false;

}

?只要能夠確保當(dāng)前棋局的狀態(tài)在自己下過(guò)棋之后，能夠是必?cái)?，則一定必勝。

使用鍵值對(duì)來(lái)記錄狀態(tài)。（動(dòng)態(tài)規(guī)劃）

如果對(duì)于當(dāng)前的棋盤狀態(tài)，以前有記錄的話，可以直接查詢。

當(dāng)前狀態(tài)，棋盤上只有一個(gè)o，那么一定是必?cái)B(tài)，遞歸的出口之一。

如果可以繼續(xù)下棋，那么就要找出最優(yōu)方案（下一步一定是必?cái)B(tài)的）。

可以選擇放置一個(gè)或兩個(gè)棋子。

對(duì)于整個(gè)棋盤進(jìn)行遍歷，找到所有能夠下棋子的位置，進(jìn)行探索，如果將棋子下在該處，其下一個(gè)狀態(tài)為必?cái)B(tài)，則這個(gè)狀態(tài)就一定是必勝態(tài)，返回true。

如果已經(jīng)探索了所有的位置，但是仍然沒(méi)有返回，那么就說(shuō)明，現(xiàn)在一定是必?cái)　?/p>

柚子快報(bào)激活碼778899分享：算法 【藍(lán)橋杯】滅鼠先鋒

http://yzkb.51969.com/

參考鏈接