题意:给你1个20*20的格子图,有的是障碍有的是怪,你可以每次指定上下左右的方向,然后所有怪都会向那个方向走,
如果2个怪撞上了,就融合在一起,让你给不超过5w步,让所有怪都融合
题解:我们可以选择一个边角的位置,每次都让一个怪移动到那里,同时暴力维护剩下的怪的位置,暴力走就可以了
不过后面发现好像直接随机也能过去？ 下面我们队3个人的...
#include <iostream>
#include<string>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
char puzzle[][];
int kangaroo[][];
bool tag[][];
string ans;
int n, m;
const int a[][] = { {,},{-,},{,},{,-} };
const string moving[] = { "D","U","R","L" };
struct node {
int x, y;
string c;
};
node start;
queue<node> fuck;
string moveway[][];
string addmove(int x)
{
if (x == )
return moving[];
if (x == )
return moving[];
if (x == )
return moving[];
return moving[];
}
bool check(int x, int y)
{
if (x > && x <= n && y > && y <= m && puzzle[x][y] != '')
return true;
else
return false;
}
int guess_sum=;
bool check_around(int x, int y)
{
int sum = ,j;
for (int i = ; i < ; i++)
{
int ax = x + a[i][];
int ay = y + a[i][];
if (check(ax, ay) && kangaroo[ax][ay] == )
{
sum++;
j = i;
}
}
if (sum==)
{
guess_sum = j;
return true;
}
else
return false;
}
void BFS()
{
while (!fuck.empty())
{
node tmp = fuck.front();
fuck.pop();
for (int i = ; i < ; i++)
{
int x = tmp.x + a[i][];
int y = tmp.y + a[i][];
if (check(x, y) && kangaroo[x][y] == && tag[x][y] == false)
{
node new_node;
new_node.x = x;
new_node.y = y;
new_node.c = addmove(i) + tmp.c;
moveway[x][y] = new_node.c;
tag[x][y] = true;
fuck.push(new_node);
}
}
}
}
node needmove;
bool judge()
{
needmove.c = "";
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++)
if (i != start.x || j != start.y)
{
if (kangaroo[i][j] > )
{
if (needmove.c == "" || needmove.c.size() < moveway[i][j].size())
{
needmove.x = i;
needmove.y = j;
needmove.c = moveway[i][j];
}
}
}
if (needmove.c != "")
return false;
return true;
}
void movex(int& x, int y, char c)
{
if (c == 'U'&&x - > && puzzle[x - ][y] != '')
x--;
if (c == 'D'&&x + <= n && puzzle[x + ][y] != '')
x++;
}
void movey(int x, int& y, char c)
{
if (c == 'L'&&y - > && puzzle[x][y - ] != '')
y--;
if (c == 'R'&&y + <= m && puzzle[x][y + ] != '')
y++;
}
void movekangaroo()
{
int tmp[][];
for (int k = ; k < needmove.c.size(); k++)
{
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++)
tmp[i][j] = kangaroo[i][j];
char c = needmove.c[k];
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++)
if (kangaroo[i][j] > )
{
int newx = i, newy = j;
tmp[i][j] = ;
movex(newx, newy, c);
movey(newx, newy, c);
tmp[newx][newy] = ;
}
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++)
kangaroo[i][j] = tmp[i][j];
}
}
int len = ;
int main()
{
int i, j, k;
ios::sync_with_stdio(false);
cin.tie();
cin >> n >> m;
for (i = ; i <= n; i++)
for (j = ; j <= m; j++)
cin >> puzzle[i][j];
memset(kangaroo, , sizeof(kangaroo));
int sum = ;
for (i = ; i <= n; i++)
for (j = ; j <= m; j++)
if (puzzle[i][j] == '')
{
sum++;
kangaroo[i][j] = ;
}
if (sum == || sum == )
{
cout << "L\n";
return ;
}
for (i = ; i <= n; i++)
for (j = ; j <= m; j++)
if (kangaroo[i][j] == && check_around(i, j))
{
start.x = i;
start.y =j;
start.c = "";
}
for (i = ; i <= n; i++)
for (j = ; j <= m; j++)
moveway[i][j] = "";
memset(tag, false, sizeof(tag));
fuck.push(start);
tag[start.x][start.y] = true;
BFS();
/*for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
if (kangaroo[i][j] > 0)
cout << i << " " << j << " " << moveway[i][j] << endl;
}*/
ans = "";
while (!judge() && len < ) //get needmove
{
len += needmove.c.size();
ans += needmove.c;
movekangaroo();
/* cout << needmove.x << " " << needmove.y << " "<<needmove.c<<endl;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
cout << puzzle[i][j];
for (j = 1; j <= 20; j++)
cout << " ";
for (j = 1; j <= m; j++)
cout << kangaroo[i][j];
cout << endl;
}
cout << endl;*/
}
if (len == )
ans = ans + "R";
cout << ans << "\n";
}
#include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define sl(x) scanf("%lld",&x)
using namespace std;
ll s[][];
int main()
{
ll n,m,i,j,k;
sl(n);sl(m);
for(i = ;i < n;i++)
scanf("%s",s[i]);
srand(time());
char ans[] = {'L','R','D','U'};
int l = ,r = ;
for(i = ;i <= ;i++)
{
char ch = ans[rand()%];
printf("%c",ch);
}
puts("");
return ;
}
#include<bits/stdc++.h> using namespace std; #define mem(a,i) memset(a,i,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
const int maxn=;
int n,m;
char s[maxn][maxn];
int a[maxn][maxn];
int b[maxn][maxn];
int p[]={,,,-};
int q[]={,-,,};
char ch[]={'L','R','U','D'};
int deg(int x,int y) {
int res=;
rep(i,,) {
int xx=x+p[i];
int yy=y+q[i];
if(xx<||xx>=n||yy<||yy>=m) continue;
if(s[xx][yy]=='') continue;
res++;
}
return res;
}
struct Node {
int x,y;
int step;
Node() {}
Node(int _x,int _y,int _step) {
x=_x;
y=_y;
step=_step;
}
};
bool vis[maxn][maxn];
int f[maxn][maxn];
queue<Node> Q; int main() {
scanf("%d%d",&n,&m);
rep(i,,n-) scanf("%s",s[i]);
int ex,ey;
int sum=;
rep(i,,n-) {
rep(j,,m-) {
if(s[i][j]=='') a[i][j]=;
else {
a[i][j]=;
sum++;
}
}
}
if(sum==) return *puts("");
rep(i,,n-) {
rep(j,,m-) {
if(s[i][j]==''&°(i,j)==) {
ex=i;
ey=j;
}
}
}
// printf("%d %d\n",ex,ey);
// puts("");
int epoch=;
int t=;
while(t<=) {
if(a[ex][ey]==sum) break;
mem(vis,);
mem(f,-);
while(!Q.empty()) Q.pop();
Node start(ex,ey,);
Q.push(start);
vis[ex][ey]=;
int sx=ex,sy=ey,step=;
while(!Q.empty()) {
Node o=Q.front();
Q.pop();
if(step<o.step&&a[o.x][o.y]) {
step=o.step;
sx=o.x;
sy=o.y;
}
rep(i,,) {
int x=o.x+p[i];
int y=o.y+q[i];
if(x<||x>=n||y<||y>=m) continue;
if(s[x][y]==''||vis[x][y]) continue;
Node node(x,y,o.step+);
f[x][y]=i;
vis[x][y]=;
Q.push(node);
}
}
// printf("%d %d\n",sx,sy);
// rep(i,0,n-1) {
// rep(j,0,m-1) {
// printf("%d ",a[i][j]);
// }
// puts("");
// }
while() {
if(sx==ex&&sy==ey) break;
int o=f[sx][sy];
printf("%c",ch[o]);
// printf("%d %d\n",sx,sy);
t++;
mem(b,);
rep(i,,n-) {
rep(j,,m-) {
if(s[i][j]=='') continue;
int x=i-p[o];
int y=j-q[o];
if(x<||x>=n||y<||y>=m||s[x][y]=='') {
b[i][j]+=a[i][j];
}
else {
b[x][y]+=a[i][j];
}
}
}
rep(i,,n-) {
rep(j,,m-) {
a[i][j]=b[i][j];
}
}
sx=sx-p[o];
sy=sy-q[o];
}
}
puts("");
return ;
}