Gym - 100783E

标题:n個のロボット(4個を超えない)があって、ロボットはすべて障害物あるいはロボットにぶつかってやっと止まったので、さもなくばもとの方向に沿ってまっすぐ行って、4個のロボットはすべて移動することができて、最低で何歩移動することを求めて、ロボット1は出口(X)に着くことができます
考え方:BFSは、タイトル制限が死んでステップ数に制限があるということで、これはつまり枝切りなので、普通は問題がなければタイムアウトしないので、それから毎回の状態を記録するには、int型の数で記録することができます.地図は<10*10なので、座標値ごとに1つの10を掛けると必ず10未満になるので、これを用いて重さを判断することができます.そしてロボットの歩く方向を列挙すればいいのです

 1 #include 
 2 #include 
 3 #include 
 4 #include <string.h>
 5 using namespace std;
 6 #define jud(x,y) x>=1&&x<=w&&y>=1&&y<=h&&graph[x][y]=='.'
 7 
 8 int n,h,w,l,ex,ey;
 9 bool vis[100000000];
10 char graph[50][50];
11 int dic[4][2]={
     1,0,-1,0,0,1,0,-1};
12 
13 class Node{
14 public :
15     int step;
16     int x[5],y[5];
17     int getlocate()
18     {
19         int tmp = 0;
20         for(int i = 1 ; i <= n ; i++)
21             tmp = tmp*10+x[i];
22         for(int i = 1 ; i <= n ;i++)
23             tmp = tmp*10+y[i];
24         return tmp;
25     }
26 }node;
27 
28 void bfs()
29 {
30     node.step = 0;
31     queues;
32     Node a,b;
33     s.push(node);
34     vis[node.getlocate()] = true;
35     while(!s.empty())
36     {
37         a = s.front();
38         s.pop();
39         if(a.step>l)
40             continue;
41         if(a.x[1]==ex&&a.y[1]==ey)
42             {
43                 printf("%d
",a.step);
44                 return;
45             }
46         for(int i = 1;i<=n;i++)
47             graph[a.x[i]][a.y[i]] = i+'0';
48         for(int i = 1;i<=n;i++)
49         {
50             graph[a.x[i]][a.y[i]] = '.';
51             for(int j = 0;j<4;j++)
52             {
53 
54                 b = a;
55                 b.step++;
56                 while(jud(b.x[i]+dic[j][0],b.y[i]+dic[j][1]))
57                 {
58                     b.x[i] += dic[j][0];
59                     b.y[i] += dic[j][1];
60                 }
61                 if(!vis[b.getlocate()])
62                 {
63                     vis[b.getlocate()] = true;
64                     s.push(b);
65                  //   printf("%d %d
",b.getlocate(),b.step);
66                 }
67             }
68            graph[a.x[i]][a.y[i]] = i+'0';
69         }
70         for(int i = 1;i<=n;i++)
71             graph[a.x[i]][a.y[i]] = '.';
72     }
73     printf("NO SOLUTION
");
74 }
75 
76 
77 int main()
78 {
79     scanf("%d%d%d%d",&n,&h,&w,&l);
80     for(int i = 1;i <= w ; i++)
81     {
82         scanf("%s",graph[i]+1);
83         for(int j = 1 ; j <= h ; j++)
84             if(graph[i][j]>='1'&&graph[i][j]<='4')
85             {
86                  node.x[graph[i][j]-'0'] = i;
87                  node.y[graph[i][j]-'0'] = j;
88                  graph[i][j] = '.';
89             }else if(graph[i][j]=='X')
90             ex = i,ey = j,graph[i][j]='.';
91     }
92     bfs();
93     return 0;
94 }

 
転載先:https://www.cnblogs.com/Tree-dream/p/6958996.html