HDU-1072

2018-03-01

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1072

题目大意

从起始地点到终点，最多走6步，中途某些格子可以将步数加回6。问最少多少步能走出去。

思想

这个题相比上一个题，这个题相对简单但是被坑了更久，基本没什么需要多想的，但是卡在了一些小细节上。
比如，这个题也有状态的记录和判重。一开始我用的是当前点坐标和上一个点的坐标和方向来作为记录的状态，后来看了题解后发现是用的当前点的坐标和剩余的步数。所以，哪些参数可以用来确定状态还需要思考。

第二个卡住的地方是now.time和now.spend的位置。我一开始认为，在for循环时，pre不会变，所以now也不会变，所以就把now.time和now.spend的赋值语句放在了for外面。但是，当其中某一步走到时间重置点时，如果放在外面的话，now.time就会在接下来的for循环中一直是6。显然是不对的。。。就这一点卡了一个多小时。。很难受。。在比赛中这就凉了。。

代码

HDU-1072

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int N,M,sx,sy;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool used[10][10][7];
int mmap[10][10];
struct Node{
    int x,y;
    int time;
    int spend;
};
int bfs()
{
    queue<Node> q;
    memset(used,0,sizeof(used));
    while (!q.empty()) q.pop();
    Node first;
    first.x=sx; first.y=sy; first.time=6; first.spend=0;
    q.push(first);
    used[sx][sy][10]=true;
    while (!q.empty())
    {
        Node now,pre;
        pre=q.front();
        q.pop();
        if (mmap[pre.x][pre.y] == 3) return pre.spend;
        if (pre.time == 1) continue;
        int xx,yy;
        for (int i=0;i<4;i++)
        {
            xx=pre.x+dx[i];
            yy=pre.y+dy[i];
            if (xx>0 && xx<=N && yy>0 && yy<=M)
            {
                now.x=xx; now.y=yy;
                if (mmap[xx][yy] == 0) continue;
    //            printf("(%d,%d)->(%d,%d)\n",pre.x,pre.y,now.x,now.y);
                now.time=pre.time-1;
                now.spend=pre.spend+1;
                if (mmap[xx][yy] == 4) now.time=6;
                if (used[xx][yy][now.time]) continue;
                used[xx][yy][now.time]=true;
                q.push(now);
            }
        }
    }
    return -1;
}
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&N,&M);
        for (int i=1;i<=N;i++)
            for (int j=1;j<=M;j++)
            {
                scanf("%d",&mmap[i][j]);
                if (mmap[i][j] == 2)
                {
                    sx=i; sy=j;
                }
            }
        printf("%d\n",bfs());
    }
    return 0;
}

后记

一会去看权游。。今天一天只做了两道题。。确实虚了。。坚持每天做~忙碌的半年啊~