一个N × M的2D迷宫中有两个机器人。机器人A在迷宫左上角，只能向右或向下移动；机器人B在迷宫右下角，只能向左或向上移动。机器人不能移动到迷宫外。此外，由于奇怪的同步机制，这两个机器人只能同时向相反的方向移动。也就是说或者机器人A向右同时机器人B向左；或者机器人A向下同时机器人B向上移动。
迷宫中有一些格子存在障碍，机器人不能移动到有障碍的格子上。如果某个机器人的移动方向上的下一个格子有障碍，它会停在当前格子上；这时另一个机器人不受影响，仍能向相反方向移动。迷宫范围之外可以视为全部都是障碍。
此外，两个机器人在移动中不能“相撞”。相撞是指：
两个机器人同时处在同一个格子上；
两个机器人在一次移动中互换位置。
小Hi想知道，最少经过多少次移动可以使机器人A走到右下角，同时机器人B走到左上角。
第一行包含两个正整数N和M。 (1 ≤ N, M ≤ 50)
以下是一个N × M的01矩阵，其中0表示格子上没有障碍，1表示格子上有障碍。
1 x u
2 x
第一种表示将第x号节点的权值修改为u
第二种表示询问以第x号节点为根的子树中，最小的权值是多少。
对于30%的数据，1 ≤ N, Q ≤ 1000
对于100%的数据，1 ≤ N, Q ≤ 100000, -109 <= Vi, u <= 109
输出一个整数代表最少移动的步数。如果目标不能达成，输出-1。
样例输入 5 5 00001 00000 00100 01000 00000 样例输出 9 题解直接搜索。。。
#include <queue> #include <cmath> #include <cstdio> #include <complex> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define ll long long #define inf 1000000000 #define PI acos(-1) #define bug puts("here") #define REP(i,x,n) for(int i=x;i<=n;i++) #define DEP(i,n,x) for(int i=n;i>=x;i--) #define mem(a,x) memset(a,x,sizeof(a)) using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<\'0\'||ch>\'9\'){if(ch==\'-\') f=-1;ch=getchar();} while(ch>=\'0\'&&ch<=\'9\'){x=x*10+ch-\'0\';ch=getchar();} return x*f; } inline void Out(int a){ if(a<0) putchar(\'-\'),a=-a; if(a>=10) Out(a/10); putchar(a%10+\'0\'); } const int N=55; char map[N][N]; bool vis[N][N][N][N]; int next1[2][2]={1,0,0,1}; int next2[2][2]={-1,0,0,-1}; int n,m; struct node{ int x1,y1; int x2,y2; int step; node(){} node(int t1,int t2,int t3,int t4){ x1=t1;y1=t2; x2=t3;y2=t4; step=0; } }; int bfs(){ queue<node>que; node tmp=node(1,1,n,m),cur; vis[1][1][n][m]=true; que.push(tmp); while(!que.empty()){ cur=que.front();que.pop(); if(cur.x1==n&&cur.y1==m&&cur.x2==1&&cur.y2==1) return cur.step; REP(i,0,1){ tmp.x1=cur.x1+next1[i][0]; tmp.y1=cur.y1+next1[i][1]; tmp.x2=cur.x2+next2[i][0]; tmp.y2=cur.y2+next2[i][1]; if(tmp.x1==tmp.x2&&tmp.y1==tmp.y2) continue; if(tmp.x1==cur.x2&&tmp.y1==cur.y2) continue; if(tmp.x1<1||tmp.x1>n||tmp.y1<1||tmp.y1>m) tmp.x1=cur.x1,tmp.y1=cur.y1; if(tmp.x2<1||tmp.x2>n||tmp.y2<1||tmp.y2>m) tmp.x2=cur.x2,tmp.y2=cur.y2; if(map[tmp.x1][tmp.y1]==\'1\') tmp.x1=cur.x1,tmp.y1=cur.y1; if(map[tmp.x2][tmp.y2]==\'1\') tmp.x2=cur.x2,tmp.y2=cur.y2; if(vis[tmp.x1][tmp.y1][tmp.x2][tmp.y2]) continue; vis[tmp.x1][tmp.y1][tmp.x2][tmp.y2]=true; tmp.step=cur.step+1; que.push(tmp); } } return -1; } int main() { n=read();m=read(); REP(i,1,n) scanf("%s",map[i]+1); printf("%d\n",bfs()); return 0; }