首页 > 代码库 > hdu 2821 学习一点dfs的小技巧吧。。 还是自己太弱了
hdu 2821 学习一点dfs的小技巧吧。。 还是自己太弱了
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int r,c,s,flag;int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};char mapp[25][25],road[1000],d[5] = {"DURL"};bool check(int x,int y){ if(x < 0 || x >= r || y < 0 || y >= c) return false; return true;}void dfs(int x,int y,int num) //表示出发位置为(x,y),已经消灭了num个箱子{ if(num >= s) { road[num] = 0; flag = 1; return; } for(int k = 0; k < 4; k++) { int i = x + dir[k][0]; int j = y + dir[k][1]; if(!check(i,j) || mapp[i][j]) continue; //(1)下一步就走出界外,或者与箱子之间没有空格 while(check(i,j) && !mapp[i][j])//(2)对于不能临时改变方向的搜索这个方法比较适用 i += dir[k][0], j += dir[k][1]; if(!check(i + dir[k][0],j + dir[k][1])) continue; //到达棋盘边缘,不能推 int t = mapp[i][j]; mapp[i+dir[k][0]][j+dir[k][1]] += t - 1; mapp[i][j] = 0; road[num] = d[k]; dfs(i,j,num+1); if(flag) return; mapp[i+dir[k][0]][j+dir[k][1]] -= t - 1;//状态的恢复过程 mapp[i][j] = t; }}int main(){ while(scanf("%d%d",&c,&r)!=EOF) { s = flag = 0; for(int i = 0; i < r; i++) { getchar(); scanf("%s",mapp[i]); for(int j = 0; j < c; j++) { if(mapp[i][j] == ‘.‘) mapp[i][j] = 0; else mapp[i][j] -= ‘a‘ - 1; s += mapp[i][j]; } } for(int i = 0; i < r; i++) { if(flag) break; for(int j = 0; j < c; j++) { if(mapp[i][j]) continue; dfs(i,j,0); if(flag == 1) { printf("%d\n%d\n",i,j); printf("%s\n",road); break; } } } } return 0;}
hdu 2821 学习一点dfs的小技巧吧。。 还是自己太弱了
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。