題目鏈接：

https://www.luogu.org/problemnew/show/P3956

這個題只要注意一下深度優(yōu)先搜索或者是寬度優(yōu)先搜索剪支就行了。純粹的暴力搜索是不行的，還要注意一下只有一個空格的時候是恒為零的就行了。

以下代碼是寬度優(yōu)先搜索：

#include <iostream> #include <stdio.h> #include <cstring> #include <queue> using namespace std; struct node {bool flag;int color;pair<int ,int>temp;int value;int hei; }arr[120][120]; int x[5]={0,1,0,-1}; int y[5]={1,0,-1,0};int main() {int m,n;int fuyi=-1; //判斷是不是可以達到。queue <node>que;scanf("%d %d",&m,&n);if(m==1){cout<<0<<endl;goto xxx;}memset(arr,-1,sizeof(arr));for(int i=0;i<120;i++)for(int j=0;j<120;j++){arr[i][j].temp.first=i;arr[i][j].temp.second=j;arr[i][j].flag=false;arr[i][j].value=~(1<<31);}arr[1][1].value=0;for(int i=0;i<n;i++){int a,b;scanf("%d %d",&a,&b);scanf("%d",&arr[a][b].color);arr[a][b].flag=true;}que.push(arr[1][1]);while(!que.empty()){node temp=que.front();que.pop();arr[temp.temp.first][temp.temp.second].hei=100;for(int i=0;i<4;i++){int thex=temp.temp.first;int they=temp.temp.second;int thex1=thex+x[i];int they1=they+y[i];if(thex1<=m&&thex1>=1&&they1>=1&&they1<=m&&arr[thex1][they1].hei!=100) //加入的時候判定一下hei是不是等于負一。{if(temp.flag==true){if(thex1==m&&they1==m)fuyi=100; //其中的邏輯問題嗎if(arr[thex1][they1].flag==false){if(temp.value+2<arr[thex1][they1].value){arr[thex1][they1].value=temp.value+2;arr[thex1][they1].color=arr[thex][they].color;que.push(arr[thex1][they1]);}}else if(arr[thex1][they1].color==arr[thex][they].color){//顏色相等。if( temp.value<arr[thex1][they1].value ) //這里。{arr[thex1][they1].value=temp.value;que.push(arr[thex1][they1]);}}else//顏色不等。{if(temp.value+1<arr[thex1][they1].value){arr[thex1][they1].value=temp.value+1;que.push(arr[thex1][they1]);}}}else //說明是當前的位置是施魔法得來的。{if(thex1==m&&they1==m&&arr[thex1][they1].flag==true)fuyi=100;if(arr[thex1][they1].flag==false){}else if(arr[thex1][they1].color==arr[thex][they].color) //對啊。魔法而來。{if( temp.value<arr[thex1][they1].value ) //這里。{arr[thex1][they1].value=temp.value;que.push(arr[thex1][they1]);}}else{if(temp.value+1<arr[thex1][they1].value){arr[thex1][they1].value=temp.value+1;que.push(arr[thex1][they1]);}}}}}}if(fuyi!=100){cout<<-1<<endl;}else{cout<<arr[m][m].value<<endl;}xxx:;return 0; }

?

總結

以上是生活随笔為你收集整理的noip 2017棋盘的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。