1.6.4 棋盤問題2

數據的第一行包含兩個正整數m，n，以一個空格分開，分別代表棋盤的大小，棋盤上有顏色的格子的數量。

接下來的n 行，每行三個正整數x，y，c，分別表示坐標為（x，y）的格子有顏色c。

其中c=1 代表黃色，c=0 代表紅色。相鄰兩個數之間用一個空格隔開。棋盤左上角的坐標為（1, 1），右下角的坐標為（m, m）。

棋盤上其余的格子都是無色。保證棋盤的左上角，也就是（1，1）一定是有顏色的。

輸出格式：

輸出一行，一個整數，表示花費的金幣的最小值，如果無法到達，輸出-1。輸入輸出樣例

輸入樣例#1：

5 7

1 1 0

1 2 0

2 2 1

3 3 1

3 4 0

4 4 1

5 5 0

輸出樣例#1：

8

輸入樣例#2：

5 5

1 1 0

1 2 0

2 2 1

3 3 1

5 5 0

輸出樣例#2：

-1

說明

輸入輸出樣例1

說明

從（1，1）開始，走到（1，2）不花費金幣

從（1，2）向下走到（2，2）花費1 枚金幣

從（2，2）施展魔法，將（2，3）變為黃色，花費2 枚金幣從（2，2）走到（2，3）不花費金幣

從（2，3）走到（3，3）不花費金幣

從（3，3）走到（3，4）花費1 枚金幣

從（3，4）走到（4，4）花費1 枚金幣

從（4，4）施展魔法，將（4，5）變為黃色，花費2 枚金幣，

從（4，4）走到（4，5）不花費金幣

從（4，5）走到（5，5）花費1 枚金幣

共花費8 枚金幣。

輸入輸出樣例2 說明

從（1，1）走到（1，2），不花費金幣

從（1，2）走到（2，2），花費1 金幣

施展魔法將（2，3）變為黃色，并從（2，2）走到（2，3）花費2 金幣從（2，3）走到（3，3）不花費金幣

從（3，3）只能施展魔法到達（3，2），（2，3），（3，4），（4，3）

而從以上四點均無法到達（5，5），故無法到達終點，輸出－1

數據規模與約定

對于30%的數據，1 ≤m ≤5，1 ≤n ≤10。

對于60%的數據，1 ≤m ≤20，1 ≤n ≤200。

對于100%的數據，1 ≤m ≤100，1 ≤n ≤1,000。

解題報告

這道題目是2017年普及組第三題，實質上是求矩陣中一個點到另一個點的最短路徑，對于這類型的題目，通常可以用搜索的方法來完成，深度優先和廣度優先都行，廣度優先需要使用隊列，稍微復雜一點，我這里就用深搜來完成。

1、輸入數據，構造棋盤，總共三種顏色，0表示紅色，1表示黃色，-1表示無色；

2、從（1,1）點開始，往上下左右四個方向去搜索，這里和普通的只能往右和左搜索的題目有點不同，在普通的搜索里面，到達了一個點就設一個標志變量，然后下次就不再搜索這個節點，但是這里不能這么簡單的處理，因為每個節點可以往上下左右四個方向搜索，如果不設標志則會形成死循環，出不來，設個標志則有可能從不同的路徑走到這個點的花費可能不相同，第一次的花費不一定是最低的。那么我們就把進到這個節點的花費記錄下來，下次進入這個節點時候，比較一下花費，如果相同或者大于上次花費，就不用搜索這個節點，否則就繼續搜索他，我們把這種方法叫做記憶化搜索。

3、對于魔法問題，我們采用一點貪心策略，碰到一個無色格子，就讓他變得和當前格子顏色一樣，再到深搜遞歸函數里面加上一個參數，來表示魔法狀態，如果上次已經使用了魔法，而當前格子是無色，也需要使用魔法，因為不能兩次使用魔法，就直接返回。

4、當走到了右下角（m,m）點，說明已經找到了一條路徑，把花費最小那條路徑記錄下來就OK了。

方法一:

#include

#include

//本代碼可以把所有vis刪去，不影響運行結果

//本代碼可以把所有vis刪去，不影響運行結果

//本代碼可以把所有vis刪去，不影響運行結果

int m,n;//棋盤大小，有色格子

int map[101][101];//棋盤數據

int step[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//移動方向

int ans=0xFFFFFFF;//答案，花費最少金幣數

int d[101][101];//到達某個格子花費的最少金幣數

int vis[101][101];//標記走過的格子

//橫、縱坐標，是否使用過魔法，花費金幣總數

void dfs(int x,int y,bool magic,int sum)

{//如果這次走到(x,y)花的金幣不比之前搜索的少，必定不是最優解

if(sum>=d[x][y]) return;

//否則更新最優解

d[x][y]=sum;

//判斷是否到終點，是則更新答案

if(x==m && y==m){

ans=std::min(sum,ans);

return;

}

//否則開始枚舉往四個方向走

int X,Y;

for(int i=0;i<4;i++)

{//計算下個格子坐標

X=x+step[i][0];

Y=y+step[i][1];

//判斷下標越界，判斷重復訪問

if(X<1||X>m||Y<1||Y>m||vis[X][Y]) continue;

//如果是空格

if(map[X][Y]==2){

//如果上次使用過魔法，此路不通

if(magic) continue;

else {//上次沒用魔法，可以用

vis[X][Y]=true;//標記

//因為要花最少金幣，所以指定顏色和過來的格子一樣

map[X][Y]=map[x][y];

dfs(X,Y,true,sum+2);//走到下一個格子上

map[X][Y]=2;//恢復空白

}

}

//如果不是空格

else if(map[X][Y]!=2){

vis[X][Y]=true;//標記

if(map[x][y]==map[X][Y]){//顏色相同

dfs(X,Y,false,sum);

}

else dfs(X,Y,false,sum+1);//顏色不同

}

//回溯

vis[X][Y]=false;

}

return;

}

int main()

{//初始化

for(int i=0;i<101;i++)

{

for(int j=0;j<101;j++)

{

map[i][j]=2;//全是空格

d[i][j]=0xFFFFFFF;//全是最大值

vis[i][j]=false;//全是未訪問

}

}

scanf("%d%d",&m,&n);

int x,y;

while(n)

{//給指定格子涂色

scanf("%d%d",&x,&y);

scanf("%d",&map[x][y]);

--n;

}

vis[1][1]=true;//先行標記起點

dfs(1,1,false,0);//傳初態

if(ans!=0xFFFFFFF) printf("%d",ans);//如果有解

else printf("-1");//如果無解

return 0;

}

視頻接入服務 VIS

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。