Gym - 101981K The 2018 ICPC Asia Nanjing Regional Contest K.Kangaroo Puzzle 暴力或随机-白红宇

Gym - 101981K The 2018 ICPC Asia Nanjing Regional Contest K.Kangaroo Puzzle 暴力或随机

阅读量：7098 次

发布时间：2019-06-28

本文共 8137 字，大约阅读时间需要 27 分钟。

题意:给你1个20*20的格子图,有的是障碍有的是怪,你可以每次指定上下左右的方向,然后所有怪都会向那个方向走,

如果2个怪撞上了,就融合在一起,让你给不超过5w步,让所有怪都融合

题解:我们可以选择一个边角的位置,每次都让一个怪移动到那里,同时暴力维护剩下的怪的位置,暴力走就可以了

不过后面发现好像直接随机也能过去？下面我们队3个人的...

1 #include 
     
        2 #include
      
         3 #include
       
          4 #include
          5 #include
         
            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
          
            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 needmove190 {191 len += needmove.c.size();192 ans += needmove.c;193 movekangaroo();194 /* cout << needmove.x << " " << needmove.y << " "<
           
            <

1 #include
     
       2 #define ll long long 3 #define PII pair
      
        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
     
        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
      
        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
       
        =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 }