題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)n*m的矩陣，每個(gè)點(diǎn)都有一個(gè)顏色，顏色的種類不超過(guò)40種，如果想從一個(gè)點(diǎn)到達(dá)另一個(gè)點(diǎn)，有兩種方法：

花費(fèi)一個(gè)單位的時(shí)間從某種顏色閃現(xiàn)到相同的顏色

花費(fèi)一個(gè)單位的時(shí)間走到相鄰的格子中

現(xiàn)在給出 q 個(gè)詢問(wèn)，每次詢問(wèn)回答從起點(diǎn)到終點(diǎn)的最短時(shí)間

題目分析：因?yàn)?q 高達(dá) 1e5 ，所以限制了每次詢問(wèn)必須在 O(1) ~ O(logn) 的時(shí)間復(fù)雜度內(nèi)回答，所以我們必須預(yù)處理，這種題目是第一次見(jiàn)，直接說(shuō)怎么做吧，首先我們需要預(yù)處理出 dis[ color ][ x ][ y ] 數(shù)組，代表的是從點(diǎn) ( x , y ) 到 color 顏色的最短路，這樣對(duì)于每個(gè)詢問(wèn)，我們就可以以每個(gè)顏色為中轉(zhuǎn)點(diǎn)維護(hù)最小值了，在預(yù)處理時(shí)和普通的bfs寫(xiě)法大同小異，無(wú)非就是每次更新時(shí)可能加入多個(gè)起點(diǎn)，并且同時(shí)需要維護(hù)多個(gè)狀態(tài)，具體實(shí)現(xiàn)可以參照代碼，并不是很難

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e3+100;const int b[4][2]={0,1,0,-1,1,0,-1,0};struct Node {int x,y;Node(int x,int y):x(x),y(y){}; };int maze[N][N],n,m,k;vector<Node>color[45];//color[k]:(x,y)int dis[45][N][N];//dis[color][x][y]bool vis[N][N],vis_color[45];void bfs(int id) {memset(vis,false,sizeof(vis));memset(vis_color,false,sizeof(vis_color));queue<Node>q;for(int i=0;i<color[id].size();i++){int x=color[id][i].x,y=color[id][i].y;q.push(Node(x,y));vis[x][y]=true;dis[id][x][y]=0;}vis_color[id]=true;while(q.size()){Node cur=q.front();q.pop();int x=cur.x,y=cur.y;if(!vis_color[maze[x][y]])//使用閃現(xiàn) {vis_color[maze[x][y]]=true;for(int i=0;i<color[maze[x][y]].size();i++){int xx=color[maze[x][y]][i].x,yy=color[maze[x][y]][i].y; if(vis[xx][yy])continue; q.push(Node(xx,yy));vis[xx][yy]=true;dis[id][xx][yy]=dis[id][x][y]+1;}}for(int i=0;i<4;i++)//不使用閃現(xiàn) {int xx=x+b[i][0];int yy=y+b[i][1];if(xx<=0||xx>n||yy<=0||yy>m)continue;if(vis[xx][yy])continue;vis[xx][yy]=true;q.push(Node(xx,yy));dis[id][xx][yy]=dis[id][x][y]+1;}} }int main() { //#ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); //#endif // ios::sync_with_stdio(false);scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&maze[i][j]);color[maze[i][j]].push_back(Node(i,j));}for(int i=1;i<=k;i++)//預(yù)處理bfs(i);int q;scanf("%d",&q);while(q--){int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);int ans=abs(x1-x2)+abs(y1-y2);for(int i=1;i<=k;i++)ans=min(ans,dis[i][x1][y1]+dis[i][x2][y2]+1);printf("%d\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1301F Super Jaber(bfs)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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