棋盤（dfs+剪枝）

題目描述
有一個m×mm×m的棋盤，棋盤上每一個格子可能是紅色、黃色或沒有任何顏色的。你現在要從棋盤的最左上角走到棋盤的最右下角。

任何一個時刻，你所站在的位置必須是有顏色的（不能是無色的）， 你只能向上、 下、左、 右四個方向前進。當你從一個格子走向另一個格子時，如果兩個格子的顏色相同，那你不需要花費金幣；如果不同，則你需要花費 11個金幣。

另外， 你可以花費 22 個金幣施展魔法讓下一個無色格子暫時變爲你指定的顏色。但這個魔法不能連續使用， 而且這個魔法的持續時間很短，也就是說，如果你使用了這個魔法，走到了這個暫時有顏色的格子上，你就不能繼續使用魔法； 只有當你離開這個位置，走到一個本來就有顏色的格子上的時候，你才能繼續使用這個魔法，而當你離開了這個位置（施展魔法使得變爲有顏色的格子）時，這個格子恢復爲無色。

現在你要從棋盤的最左上角，走到棋盤的最右下角，求花費的最少金幣是多少？

輸入輸出格式
輸入格式：

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

接下來的nn行，每行三個正整數x,y,cx,y,c， 分別表示座標爲(x,y)(x,y)的格子有顏色cc。

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

棋盤上其餘的格子都是無色。保證棋盤的左上角，也就是(1,1)(1,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)走到(m,m)(m,m),要求路上的花費代價最少.
如果你從A走到B,那麼走一步的代價有三種:
1. 若方格A的顏色等於方格B的顏色,那麼花費代價爲0
2. 若方格A的顏色不同於方格B的顏色,那麼花費代價爲1.
3. 若方格B的顏色爲無色,那麼相當於使用一次魔法,且花費的代價爲2,並且下一步不可以使用魔法.

 需要考慮的情況有：

1.上一次使用了魔法,那麼這一次不能使用魔法
2.上一次使用了魔法,判斷上一個點是不是和當前點顏色一致
3.顏色相同則不需要花費代價,否則花費1點代價
4.拓展的點是無顏色,那麼我們必須使用魔法,並且花費兩點代價

另外還必須要剪枝
 

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1005;
int dis[maxn][maxn],vis[maxn][maxn],mp[maxn][maxn];
int ans=1e9,n,m;
int mov[5][2]={{1,0},{-1,0},{0,1},{0,-1}};

bool check(int x,int y){
	if(x<1||x>n||y<1||y>n||vis[x][y])
	    return false;
	return true;
} 

void dfs(int x,int y,int now,int tmp){
	if(x==n&&y==n&&tmp<ans){
		ans=tmp;
		return ;
	}
	if(tmp>=dis[x][y])//剪枝 
	    return ;
	dis[x][y]=tmp;//保存走到這一個位置，最少的步數 
	for(int i=0;i<4;i++){
		int fx=x+mov[i][0];
		int fy=y+mov[i][1];
		if(!check(fx,fy))
		    continue;
		vis[fx][fy]=1;
		if(now>=3&&mp[fx][fy]!=0){//說明上一次使用了魔法，而這一次不使用魔法 
			if((now+mp[fx][fy])%2==0)
			/*
			這個地方，如果第一步是紅色  now 是1 ，第二步是 空白的 ，染成紅色 now + 2 = 3
			再下一步如果是 紅色  now + 1 = 4 
			如果是黃色 now + 1 = 5
			 
			*/ 
			    dfs(fx,fy,mp[fx][fy],tmp);//相同顏色 
			else
			    dfs(fx,fy,mp[fx][fy],tmp+1);//不同顏色 
		}
		else if(now==1||now==2){//說明上次沒有使用魔法 
			if(mp[fx][fy]==1||mp[fx][fy]==2){//這一次也不使用魔法 
				if(mp[fx][fy]==now)//相同顏色 
				    dfs(fx,fy,mp[fx][fy],tmp);
				else
				    dfs(fx,fy,mp[fx][fy],tmp+1); //顏色不同，代價+1 
			}
			else
			    dfs(fx,fy,now+2,tmp+2);//使用了魔法，代價+2 
			    //這個地方因爲染完色的地方走完下一步就又變成空白的了，所以是 now + 2 
		}
		vis[fx][fy]=0;
	} 
}

int main(){
    scanf("%d%d",&n,&m);
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;i++){//輸入數據 
    	int x,y,num;
    	scanf("%d%d%d",&x,&y,&num);
    	mp[x][y]=num+1;
	}
	vis[1][1]=1;
	dfs(1,1,mp[1][1],0);
	if(ans==1e9)
	    printf("-1\n");
	else
	    printf("%d\n",ans);
    return 0;
}