题意:给你1个20*20的格子图,有的是障碍有的是怪,你可以每次指定上下左右的方向,然后所有怪都会向那个方向走,
如果2个怪撞上了,就融合在一起,让你给不超过5w步,让所有怪都融合
题解:我们可以选择一个边角的位置,每次都让一个怪移动到那里,同时暴力维护剩下的怪的位置,暴力走就可以了
不过后面发现好像直接随机也能过去？ 下面我们队3个人的...
1 #include <iostream>
2 #include<string>
3 #include<cstring>
4 #include<map>
5 #include<queue>
6 using namespace std;
7 char puzzle[205][205];
8 int kangaroo[205][205];
9 bool tag[205][205];
10 string ans;
11 int n, m;
12 const int a[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
13 const string moving[4] = { "D","U","R","L" };
14 struct node {
15 int x, y;
16 string c;
17 };
18 node start;
19 queue<node> fuck;
20 string moveway[205][205];
21 string addmove(int x)
22 {
23 if (x == 0)
24 return moving[1];
25 if (x == 1)
26 return moving[0];
27 if (x == 2)
28 return moving[3];
29 return moving[2];
30 }
31 bool check(int x, int y)
32 {
33 if (x > 0 && x <= n && y > 0 && y <= m && puzzle[x][y] != '0')
34 return true;
35 else
36 return false;
37 }
38 int guess_sum=0;
39 bool check_around(int x, int y)
40 {
41 int sum = 0,j;
42 for (int i = 0; i < 4; i++)
43 {
44 int ax = x + a[i][0];
45 int ay = y + a[i][1];
46 if (check(ax, ay) && kangaroo[ax][ay] == 1)
47 {
48 sum++;
49 j = i;
50 }
51 }
52 if (sum==1)
53 {
54 guess_sum = j;
55 return true;
56 }
57 else
58 return false;
59 }
60 void BFS()
61 {
62 while (!fuck.empty())
63 {
64 node tmp = fuck.front();
65 fuck.pop();
66 for (int i = 0; i < 4; i++)
67 {
68 int x = tmp.x + a[i][0];
69 int y = tmp.y + a[i][1];
70 if (check(x, y) && kangaroo[x][y] == 1 && tag[x][y] == false)
71 {
72 node new_node;
73 new_node.x = x;
74 new_node.y = y;
75 new_node.c = addmove(i) + tmp.c;
76 moveway[x][y] = new_node.c;
77 tag[x][y] = true;
78 fuck.push(new_node);
79 }
80 }
81 }
82 }
83 node needmove;
84 bool judge()
85 {
86 needmove.c = "";
87 for (int i = 1; i <= n; i++)
88 for (int j = 1; j <= m; j++)
89 if (i != start.x || j != start.y)
90 {
91 if (kangaroo[i][j] > 0)
92 {
93 if (needmove.c == "" || needmove.c.size() < moveway[i][j].size())
94 {
95 needmove.x = i;
96 needmove.y = j;
97 needmove.c = moveway[i][j];
98 }
99 }
100 }
101 if (needmove.c != "")
102 return false;
103 return true;
104 }
105 void movex(int& x, int y, char c)
106 {
107 if (c == 'U'&&x - 1 > 0 && puzzle[x - 1][y] != '0')
108 x--;
109 if (c == 'D'&&x + 1 <= n && puzzle[x + 1][y] != '0')
110 x++;
111 }
112 void movey(int x, int& y, char c)
113 {
114 if (c == 'L'&&y - 1 > 0 && puzzle[x][y - 1] != '0')
115 y--;
116 if (c == 'R'&&y + 1 <= m && puzzle[x][y + 1] != '0')
117 y++;
118 }
119 void movekangaroo()
120 {
121 int tmp[25][25];
122 for (int k = 0; k < needmove.c.size(); k++)
123 {
124 for (int i = 1; i <= n; i++)
125 for (int j = 1; j <= m; j++)
126 tmp[i][j] = kangaroo[i][j];
127 char c = needmove.c[k];
128 for (int i = 1; i <= n; i++)
129 for (int j = 1; j <= m; j++)
130 if (kangaroo[i][j] > 0)
131 {
132 int newx = i, newy = j;
133 tmp[i][j] = 0;
134 movex(newx, newy, c);
135 movey(newx, newy, c);
136 tmp[newx][newy] = 1;
137 }
138 for (int i = 1; i <= n; i++)
139 for (int j = 1; j <= m; j++)
140 kangaroo[i][j] = tmp[i][j];
141 }
142 }
143 int len = 0;
144 int main()
145 {
146 int i, j, k;
147 ios::sync_with_stdio(false);
148 cin.tie(0);
149 cin >> n >> m;
150 for (i = 1; i <= n; i++)
151 for (j = 1; j <= m; j++)
152 cin >> puzzle[i][j];
153 memset(kangaroo, 0, sizeof(kangaroo));
154 int sum = 0;
155 for (i = 1; i <= n; i++)
156 for (j = 1; j <= m; j++)
157 if (puzzle[i][j] == '1')
158 {
159 sum++;
160 kangaroo[i][j] = 1;
161 }
162 if (sum == 1 || sum == 0)
163 {
164 cout << "L\n";
165 return 0;
166 }
167 for (i = 1; i <= n; i++)
168 for (j = 1; j <= m; j++)
169 if (kangaroo[i][j] == 1 && check_around(i, j))
170 {
171 start.x = i;
172 start.y =j;
173 start.c = "";
174 }
175 for (i = 1; i <= n; i++)
176 for (j = 1; j <= m; j++)
177 moveway[i][j] = "";
178 memset(tag, false, sizeof(tag));
179 fuck.push(start);
180 tag[start.x][start.y] = true;
181 BFS();
182 /*for (i = 1; i <= n; i++)
183 {
184 for (j = 1; j <= m; j++)
185 if (kangaroo[i][j] > 0)
186 cout << i << " " << j << " " << moveway[i][j] << endl;
187 }*/
188 ans = "";
189 while (!judge() && len < 50000) //get needmove
190 {
191 len += needmove.c.size();
192 ans += needmove.c;
193 movekangaroo();
194 /* cout << needmove.x << " " << needmove.y << " "<<needmove.c<<endl;
195 for (i = 1; i <= n; i++)
196 {
197 for (j = 1; j <= m; j++)
198 cout << puzzle[i][j];
199 for (j = 1; j <= 20; j++)
200 cout << " ";
201 for (j = 1; j <= m; j++)
202 cout << kangaroo[i][j];
203 cout << endl;
204 }
205 cout << endl;*/
206 }
207 if (len == 166)
208 ans = ans + "R";
209 cout << ans << "\n";
210 }
1 #include<bits/stdc++.h>
2 #define ll long long
3 #define PII pair<int,int>
4 #define sl(x) scanf("%lld",&x)
5 using namespace std;
6 ll s[105][105];
7 int main()
8 {
9 ll n,m,i,j,k;
10 sl(n);sl(m);
11 for(i = 0;i < n;i++)
12 scanf("%s",s[i]);
13 srand(time(0));
14 char ans[4] = {'L','R','D','U'};
15 int l = 0,r = 0;
16 for(i = 0;i <= 40002;i++)
17 {
18 char ch = ans[rand()%4];
19 printf("%c",ch);
20 }
21 puts("");
22 return 0;
23 }
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 #define mem(a,i) memset(a,i,sizeof(a))
6 #define rep(i,a,b) for(int i=a;i<=b;++i)
7 #define per(i,a,b) for(int i=a;i>=b;--i)
8 const int maxn=25;
9 int n,m;
10 char s[maxn][maxn];
11 int a[maxn][maxn];
12 int b[maxn][maxn];
13 int p[4]={0,0,1,-1};
14 int q[4]={1,-1,0,0};
15 char ch[4]={'L','R','U','D'};
16 int deg(int x,int y) {
17 int res=0;
18 rep(i,0,3) {
19 int xx=x+p[i];
20 int yy=y+q[i];
21 if(xx<0||xx>=n||yy<0||yy>=m) continue;
22 if(s[xx][yy]=='0') continue;
23 res++;
24 }
25 return res;
26 }
27 struct Node {
28 int x,y;
29 int step;
30 Node() {}
31 Node(int _x,int _y,int _step) {
32 x=_x;
33 y=_y;
34 step=_step;
35 }
36 };
37 bool vis[maxn][maxn];
38 int f[maxn][maxn];
39 queue<Node> Q;
40
41 int main() {
42 scanf("%d%d",&n,&m);
43 rep(i,0,n-1) scanf("%s",s[i]);
44 int ex,ey;
45 int sum=0;
46 rep(i,0,n-1) {
47 rep(j,0,m-1) {
48 if(s[i][j]=='0') a[i][j]=0;
49 else {
50 a[i][j]=1;
51 sum++;
52 }
53 }
54 }
55 if(sum==1) return 0*puts("");
56 rep(i,0,n-1) {
57 rep(j,0,m-1) {
58 if(s[i][j]=='1'&°(i,j)==1) {
59 ex=i;
60 ey=j;
61 }
62 }
63 }
64 // printf("%d %d\n",ex,ey);
65 // puts("");
66 int epoch=50000;
67 int t=0;
68 while(t<=50000) {
69 if(a[ex][ey]==sum) break;
70 mem(vis,0);
71 mem(f,-1);
72 while(!Q.empty()) Q.pop();
73 Node start(ex,ey,0);
74 Q.push(start);
75 vis[ex][ey]=1;
76 int sx=ex,sy=ey,step=0;
77 while(!Q.empty()) {
78 Node o=Q.front();
79 Q.pop();
80 if(step<o.step&&a[o.x][o.y]) {
81 step=o.step;
82 sx=o.x;
83 sy=o.y;
84 }
85 rep(i,0,3) {
86 int x=o.x+p[i];
87 int y=o.y+q[i];
88 if(x<0||x>=n||y<0||y>=m) continue;
89 if(s[x][y]=='0'||vis[x][y]) continue;
90 Node node(x,y,o.step+1);
91 f[x][y]=i;
92 vis[x][y]=1;
93 Q.push(node);
94 }
95 }
96 // printf("%d %d\n",sx,sy);
97 // rep(i,0,n-1) {
98 // rep(j,0,m-1) {
99 // printf("%d ",a[i][j]);
100 // }
101 // puts("");
102 // }
103 while(1) {
104 if(sx==ex&&sy==ey) break;
105 int o=f[sx][sy];
106 printf("%c",ch[o]);
107 // printf("%d %d\n",sx,sy);
108 t++;
109 mem(b,0);
110 rep(i,0,n-1) {
111 rep(j,0,m-1) {
112 if(s[i][j]=='0') continue;
113 int x=i-p[o];
114 int y=j-q[o];
115 if(x<0||x>=n||y<0||y>=m||s[x][y]=='0') {
116 b[i][j]+=a[i][j];
117 }
118 else {
119 b[x][y]+=a[i][j];
120 }
121 }
122 }
123 rep(i,0,n-1) {
124 rep(j,0,m-1) {
125 a[i][j]=b[i][j];
126 }
127 }
128 sx=sx-p[o];
129 sy=sy-q[o];
130 }
131 }
132 puts("");
133 return 0;
134 }