題干：

n*m矩陣a.若a[i][j]==1則可以往左右走,若a[i][j]==0 則可以往上下走.
每一秒可以按上述規(guī)則移動(dòng),并且每秒鐘矩陣所有的值翻轉(zhuǎn)。
n*m<=1e5.問(wèn)從(sx,sy)到(tx,ty)的最短時(shí)間.

解題報(bào)告：

? 這題因?yàn)椴粠?quán)值所以不需要考慮Dijkstra，可以根據(jù)時(shí)間直接判斷狀態(tài)是0還是1。如果狀態(tài)的變換很復(fù)雜的話就考慮分層圖就好了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 3e5 + 5; int n,m; bool vis[MAX][2]; int nx[4] = {-1,1,0,0};//上，下，左，右 int ny[4] = {0,0,-1,1}; int sta[MAX]; struct Node {int x,y;int pos,t;Node(){}Node(int x,int y,int pos,int t):x(x),y(y),pos(pos),t(t){} }; inline int getp(int x,int y) {return (x-1) * m + y; } int bfs(int a,int b,int c,int d,int st,int ed) {queue<Node > q;q.push(Node(a,b,st,0));vis[st][sta[st]]=1;while(!q.empty()) {Node cur = q.front();q.pop();if(cur.pos == ed) return cur.t;int nowsta = (cur.t%2==0) ? sta[cur.pos] : 1-sta[cur.pos];if(nowsta == 0) {for(int k = 0; k<2; k++) {int tx = cur.x + nx[k];int ty = cur.y + ny[k];if(tx <1 || tx >n || ty < 1 || ty > m) continue;if(vis[getp(tx,ty)][nowsta]) continue;vis[getp(tx,ty)][nowsta] = 1 ;q.push(Node(tx,ty,getp(tx,ty),cur.t+1));}}else {for(int k = 2; k<4; k++) {int tx = cur.x + nx[k];int ty = cur.y + ny[k];if(tx <1 || tx >n || ty < 1 || ty > m) continue;if(vis[getp(tx,ty)][nowsta]) continue;vis[getp(tx,ty)][nowsta] = 1 ;q.push(Node(tx,ty,getp(tx,ty),cur.t+1));}}}return -1; } int main() {int t;cin>>t;while(t--) {scanf("%d%d",&n,&m);for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {vis[(i-1)*m+j][0]=0;vis[(i-1)*m+j][1]=0;}}for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {scanf("%d",&sta[(i-1)*m + j]);}}int stx,sty,edx,edy,st,ed;scanf("%d%d",&stx,&sty);scanf("%d%d",&edx,&edy);st = (stx-1) * m + sty;ed = (edx-1) * m + edy;int ans = bfs(stx,sty,edx,edy,st,ed);printf("%d\n",ans);}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【ZOJ - 4020 】Traffic Light （bfs，分层图）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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