$$棋盤$$

題目大意：

有一個M*M的棋盤，要從（1，1）到（m,m），中間有n個有顏色的格子，只能踩在有顏色的格子上，跳到不同顏色的格子要花費1元，可以將前方沒顏色的格子變成自己要的格子，但要花費2元（走過去還要按上述規則花錢），走出變色出來的格子后，這個格子會變回無顏色，當棋盤上有變色出來的格子時，無法再變色，從（1，1）到（m,m）最少花多少錢？如果走不到，輸出-1

解題方法：

這題我們可以用深搜，四個個數x，y，money，p，分別為行，列，用的錢，又沒有變過色，在按照提議把每一種走法套進去，還要用一個a[i][j]來記錄到（i，j）花費的錢最少是多少，當大于或等于這個數時退出，否則更新a

#include<cstdio> #include<iostream> #include<cstring> #include<string> using namespace std; int n,ans,m,a[110][110],color[110][110]; const int dx[4]={1,0,-1,0};//四個方向 const int dy[4]={0,1,0,-1};//四個方向 void dfs(int x,int y,int money,int p) {int o;if ((x==n)&&(y==n))//看看是否到結果{ans=min(ans,money);//求最小的return;}if (a[x][y]<=money) return;//剪枝else a[x][y]=money;//替換if (money>ans) return;//剪枝for (int i=0;i<4;i++)if ((x+dx[i]>0)&&(x+dx[i]<=n)&&(y+dy[i]>0)&&(y+dy[i]<=n))//看看是否出界{if (color[x][y]==color[x+dx[i]][y+dy[i]])//顏色相同{o=color[x][y];//記錄if (p) color[x][y]=0;//如果變過色，要變回去dfs(x+dx[i],y+dy[i],money,0);//用加moneycolor[x][y]=o;//再變回來}else if(color[x+dx[i]][y+dy[i]])//有顏色{o=color[x][y];//同上if (p) color[x][y]=0;dfs(x+dx[i],y+dy[i],money+1,0);//money+1color[x][y]=o;}else if(!p)//要沒變過{color[x+dx[i]][y+dy[i]]=color[x][y];//不需要考慮變哪種，如果下一步給錢的反過來還是要給錢，不用給就不用給dfs(x+dx[i],y+dy[i],money+2,1);//money+2color[x+dx[i]][y+dy[i]]=0;//清零}} } int main() {memset(a,127/3,sizeof(a));//因為要求最小的ans=a[0][0];//直接復制過去scanf("%d%d",&n,&m);int x,y,c;for (int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&c);color[x][y]=c+1;//要加1才能避免0的出現}dfs(1,1,0,0);if (ans==a[0][0]) ans=-1;printf("%d",ans); }

總結

以上是生活随笔為你收集整理的【深搜】 棋盘 【NOIp普及组 2017 第三题】 （luogu 3956/ssl 2851）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。