这个题的意识是给你一个格子, 有些格子上是空地, 有些格子有一些小球, 一个人可以从空地开始朝四个方向走, 遇到边界或者小球的时候就停止, 然后拿了一个小球后将剩下的小球推入下一个格子,如果下一个格子上面有小球的话那么将小球合并, 采用一种方案将所有的小球清除, 代码如下:
#include <bits/stdc++.h> using namespace std; int C, R; char Map[30][30]; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; char dir[] = {'R', 'L', 'D', 'U'}; bool inside(int x, int y) { return (x>=0&&x<R&&y>=0&&y<C); } string ans; bool flog; void dfs(int x, int y, string res){ //当前位置 // cout<<x<<' '<<y<<' '<<res<<endl; // for(int i=0; i<R; i++) printf("%s ", Map[i]); bool Empty = true; for(int i=0; i<R; i++) for(int j=0; j<C; j++) if(Map[i][j] != '.') { Empty = false; break; } if(Empty){ flog = true; ans = res; } bool res1 = false; for(int i=0; i<4; i++){ int nx=x, ny=y; while(inside(nx+dx[i], ny+dy[i])&&Map[nx+dx[i]][ny+dy[i]]=='.') nx=nx+dx[i], ny=ny+dy[i]; if(!inside(nx+dx[i], ny+dy[i])) continue; //走到了沟里 if(!(nx==x&&ny==y) && Map[nx+dx[i]][ny+dy[i]]!='.'){ char temp[30][30]; memcpy(temp, Map, sizeof(temp)); int bck_x = nx+dx[i], bck_y = ny+dy[i]; int bck_num = Map[bck_x][bck_y]-'a'+1; Map[bck_x][bck_y] = '.'; if(inside(bck_x+dx[i], bck_y+dy[i])){ if(Map[bck_x+dx[i]][bck_y+dy[i]] == '.' && bck_num-1!=0) Map[bck_x+dx[i]][bck_y+dy[i]] = 'a'-1+bck_num-1; else Map[bck_x+dx[i]][bck_y+dy[i]] += bck_num - 1; } dfs(bck_x, bck_y, res+dir[i]); memcpy(Map, temp, sizeof(temp)); } } } int main(){ while(scanf("%d%d", &C, &R) == 2){ for(int i=0; i<R; i++) scanf("%s", Map[i]); // for(int i=0; i<R; i++) printf("%s ", Map[i]); int res_x, res_y; flog = false; for(int i=0; i<R&&!flog; i++) for(int j=0; j<C&&!flog; j++) if(Map[i][j] == '.') { //在这里wa了两发 // if(i==4 && j==1){ // int t; // t = 0; // } dfs(i, j, ""); if(flog){ res_x = i; res_y = j; } } if(flog){ printf("%d %d ", res_x, res_y); cout<<ans<<endl; } } return 0; }