温州网站建设推广,网站建设目的主要包括哪些,网站制作台州,wordpress 的论坛题干#xff1a;
n*m矩阵a.若a[i][j]1则可以往左右走,若a[i][j]0 则可以往上下走. 每一秒可以按上述规则移动,并且每秒钟矩阵所有的值翻转。 n*m1e5.问从(sx,sy)到(tx,ty)的最短时间.
解题报告#xff1a; 这题因为不带权值所以不需要考虑Dijkstra#xff0c;可以根据…题干
n*m矩阵a.若a[i][j]1则可以往左右走,若a[i][j]0 则可以往上下走. 每一秒可以按上述规则移动,并且每秒钟矩阵所有的值翻转。 n*m1e5.问从(sx,sy)到(tx,ty)的最短时间.
解题报告 这题因为不带权值所以不需要考虑Dijkstra可以根据时间直接判断状态是0还是1。如果状态的变换很复杂的话就考虑分层图就好了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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) {queueNode 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%20) ? sta[cur.pos] : 1-sta[cur.pos];if(nowsta 0) {for(int k 0; k2; 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.t1));}}else {for(int k 2; k4; 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.t1));}}}return -1;
}
int main()
{int t;cint;while(t--) {scanf(%d%d,n,m);for(int i 1; in; i) {for(int j 1; jm; j) {vis[(i-1)*mj][0]0;vis[(i-1)*mj][1]0;}}for(int i 1; in; i) {for(int j 1; jm; 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 ;
}
