題目描述
有一個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; }