当前位置：首页 > news >正文

CH2601 电路维修（双端队列bfs）建图恶心

news 来源：原创 2024/5/3 5:08:42

CH2601 电路维修

双端队列bfs，其实就是因为只有0和1所以可以直接2维护队列单调性（和优先队列一个道理）
建图的过程需要仔细斟酌（想一想id为什么这么写）
还有，空间要开够（很玄学），我一开始N开到600一直过不了，后来必须改到700以上

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cctype>
 5 #include <queue>
 6 #include <cstring>
 7 using namespace std;
 8 
 9 #define inf 0x3f3f3f3f
10 #define res register int
11 const int N=720,M=N*N;
12 int n,m,T;
13 int head[M],ver[M*2],nxt[M*2],edge[M*2],tot;
14 int d[M*2];
15 inline int id(int i,int j){return i*(m+1)+j;}
16 // 每行m个格子，则有m+1个顶点
17 inline void add(int x,int y,int z)
18 {
19     ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; edge[tot]=z;
20     ver[++tot]=x; nxt[tot]=head[y]; head[y]=tot; edge[tot]=z;
21 }
22 
23 deque <int> q;
24 inline int bfs(int st,int ed)
25 {
26     memset(d,0x3f,sizeof(d));
27     q.push_back(st); d[st]=0;
28     while(!q.empty())
29     {
30         int x=q.front(); q.pop_front();
31         // if(d[x]!=inf) continue;
32         for(res i=head[x] ; i ; i=nxt[i])
33         {
34             int y=ver[i];
35 //            if(d[y]!=inf) continue;
36             if(d[y]>d[x]+edge[i])
37             {
38                 d[y]=d[x]+edge[i];
39                 if(edge[i]) q.push_back(y);
40                 else q.push_front(y);
41             }
42         }
43     }
44     return d[ed];
45 }
46 
47 char s[N][N];
48  
49 
50 int main()
51 {
52 //    freopen("input","r",stdin);
53     scanf("%d",&T);
54     while(T--)
55     {
56         scanf("%d %d",&n,&m);
57         tot=0;
58         memset(head,0,sizeof(head));
59         for(res i=0 ; i<n ; i++) cin>>s[i];
60         for(res i=0 ; i<n ; i++)
61             for(res j=0 ; j<m ; j++)
62             {
63                 if(s[i][j]=='/')
64                 {
65                     add(id(i+1,j),id(i,j+1),0);
66                     add(id(i,j),id(i+1,j+1),1);
67 //                    if(i==0&&j==0) printf("%")
68                 }
69                 else
70                 {
71                     add(id(i+1,j),id(i,j+1),1);
72                     add(id(i,j),id(i+1,j+1),0);
73                 }
74             }
75         int ans=bfs(id(0,0),id(n,m));
76         if(ans==inf) puts("NO SOLUTION");
77         else printf("%d\n",ans);
78     }
79     
80     return 0;    
81 }