基础的状态压缩
记下来当前的改变 , 在下一次的时候 适当的利用上次搜索的结果 下面附上 渣渣代码
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 #include<set> 9 #include<stack> 10 #include<string> 11 #include<sstream> 12 #include<map> 13 #include<cctype> 14 using namespace std; 15 int c[7],n,m,b[4][2]={0,-1,0,1,-1,0,1,0},visited[22][22],flag; 16 char a[22][22]; 17 struct node 18 { 19 int x,y; 20 }; 21 queue<node>Q; 22 bool check(int x,int y) 23 { 24 if(a[y][x]>='A'&&a[y][x]<='E') //如果是门 而且 25 { 26 if(c[a[y][x]-'A']!=0) // 钥匙不够的计划 27 return false; 28 } 29 return true; 30 } 31 void BFS(int x,int y,int &mark) 32 { 33 node q={x,y}; 34 Q.push(q); 35 while(!Q.empty()) 36 { 37 node e=Q.front(); 38 Q.pop(); 39 for(int i=0;i<4;i++) 40 { 41 q.x=e.x+b[i][0],q.y=e.y+b[i][1]; 42 if(a[q.y][q.x]!='X'&&q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&!visited[q.y][q.x]&&check(q.x,q.y)) 43 { 44 visited[q.y][q.x]=1; 45 Q.push(q); 46 if(a[q.y][q.x]>='a'&&a[q.y][q.x]<='e') 47 { 48 c[a[q.y][q.x]-'a']--; 49 if(c[a[q.y][q.x]-'a']==0) 50 mark++; 51 a[q.y][q.x]='.'; 52 } 53 if(a[q.y][q.x]=='G') 54 flag=1; 55 } 56 } 57 } 58 } 59 int main() 60 { 61 int sx,sy; 62 while(scanf("%d%d",&n,&m),(n||m)) 63 { 64 memset(c,0,sizeof(c)); 65 for(int i=0;i<n;i++) 66 { 67 for(int j=0;j<m;j++) 68 { 69 scanf(" %c",&a[i][j]); 70 if(a[i][j]=='a') 71 c[0]++; 72 if(a[i][j]=='b') 73 c[1]++; 74 if(a[i][j]=='c') 75 c[2]++; 76 if(a[i][j]=='d') 77 c[3]++; 78 if(a[i][j]=='e') 79 c[4]++; 80 if(a[i][j]=='S') 81 { 82 sx=j; 83 sy=i; 84 } 85 } 86 } 87 memset(visited,0,sizeof(visited)); 88 visited[sy][sx]=1; 89 int mark=1; 90 flag=0; 91 while(mark--) 92 { 93 while(!Q.empty()) 94 Q.pop(); 95 BFS(sx,sy,mark); 96 memset(visited,0,sizeof(visited)); 97 if(flag) 98 break; 99 } 100 if(flag) 101 printf("YES "); 102 else 103 printf("NO "); 104 } 105 return 0; 106 }