Openjudge-4115-佐助和鸣人

ゞ浴缸里的玫瑰 2021-10-25 13:22 260阅读 0赞

这一题是一道广搜的题目，首先我们通过读入字符串读入每一行，然后顺带找到鸣人的位置。

然后我们初始化之后，就进行广搜，还是广搜的格式，但是要压入队列的条件我们可以稍微变一变，我们可以直接判断下一个要走的点，是星号或者是加号，我们就判断是否走过这一点是否走过。

我们判断的依据是，假设我们走这一点，消耗零个查克拉，然后在标记数组里面查看是否为零。

这么说，你可能不明白，但是如果这一点是\#号，且查克拉大于零，我们准备走这个点，然后消耗一个查克拉，然后我们就可以去visited数组里面查找，我们是否在剩下该数目查克拉的时候走过这一点。

如果走过那就是一呗，我们广搜的时候不能搜索相同的点，也就是相同的位置，相同的查克拉，说明我们已经走过，我们不能再次返回。

但是如果查克拉的数目不一样的话，就说明，我们虽然走到了相同的位置，但是我们走的路线是不一样的，对不对。

我们在bfs搜的时候不能搜到下一层了，然后又开始回搜上一层的点，这就叫判重。

#include <iostream>
    #include <cstring>
    #include <queue>
    using namespace std;
    const int maxn=205;
    
    int m,n,t;
    int visited[maxn][maxn][15];
    char maze[maxn][maxn];
    int d[4][2]= {
        {-1,0},{1,0},{0,-1},{0,1}};
    
    struct Step {
        int x,y,t;
        int step;
        Step(int a,int b,int c,int d):x(a),y(b),t(c),step(d){}
    };
    queue <Step> q;
    
    int main()
    {
        scanf("%d%d%d",&m,&n,&t);
        Step first(0,0,0,0);
    	memset(visited,0,sizeof(visited));
        for (int i=0;i<m;i++) {
            scanf("%s",maze[i]);
            for (int j=0;j<n;j++) {
            	if (maze[i][j]=='@') {
            		first.x=i,first.y=j,first.t=t,first.step=0;
    				visited[i][j][t]=1;	
    			}	
    		}
    	}
        q.push(first);
        while (!q.empty()) {
           	Step cur=q.front();
           	q.pop();
            if (maze[cur.x][cur.y]=='+') {
                cout<<cur.step<<endl;
                return 0;
            }
            for (int i=0;i<4;i++) {
                int dx=cur.x+d[i][0];
                int dy=cur.y+d[i][1];
                if (dx<0||dy<0||dx>=m||dy>=n)
                	continue;
                if (maze[dx][dy]=='#'&&cur.t>0&&!visited[dx][dy][cur.t-1]) {
                	q.push(Step(dx,dy,cur.t-1,cur.step+1));
                	visited[dx][dy][cur.t-1]=1;
    			}
    			else if (maze[dx][dy]=='+'||maze[dx][dy]=='*'&&!visited[dx][dy][cur.t]) {
    				q.push(Step(dx,dy,cur.t,cur.step+1));
                 	visited[dx][dy][cur.t]=1;
    			}
    		}
    	}
        cout<<-1<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/xyqxyq/p/10211346.html