首页 > 代码库 > 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的小技巧吧。。 还是自己太弱了