题解 CF877D 【Olya and Energy Drinks】

zlpiscoming · 2020-01-12 15:36:23 · 题解

BFS基础题

这道题就是一个bfs,只是一次把一个方向上的所有可以取的点都存到队列里，就可以解决这个问题，当碰到墙的时候break就行了，记住要先判断这个点是否在矩阵中，然后再判断其他，不然很容易RE.

下面是我的AC代码

#include<bits/stdc++.h>
using namespace std;
char graph[1002][1002];
int vis[1002][1002] = {0};
char temp[1002];
typedef struct{
    int x,y;
    int cnt;
} point;
void bfs(int x,int y,int x2,int y2,int m,int n,int b)
{
    point temp; temp.x = x;temp.y = y; temp.cnt = 0; 
    vis[x][y] = 1;
    queue<point> a;
    a.push(temp);
    while(1){
        point temp2 = a.front();
        int h[][2] ={{0,1},{-1,0},{1,0},{0,-1}}; 
        a.pop();
        for(int j =0;j<=3;j++){
            for(int i=1;i<=b;i++){
                int dx = temp2.x+h[j][0]*i; int dy = temp2.y+h[j][1]*i;
                if(dx>=0&&dx<m&&dy>=0&&dy<n&&graph[dx][dy]=='#') break;
                if(dx>=0&&dx<m&&dy>=0&&dy<n&&vis[dx][dy]==0){
                    point temp3;
                    temp3.x = dx;
                    temp3.y = dy;
                    temp3.cnt = temp2.cnt+1;
                    a.push(temp3);
                    if(dx==x2&&dy==y2) {
                        printf("%d",temp3.cnt);
                        return;
                    }
                    vis[dx][dy] = 1;
                }
        }
    }
    if(a.empty()){
        printf("-1");
        return;
    }   
    }
}
int main(){
    int m,n,k;
    scanf("%d %d %d",&m,&n,&k);
    for(int i=0;i<m;i++){
        scanf("%s",temp);
        for(int j=0;j<n;j++){
            graph[i][j] = temp[j] ;
        }
    }
    int x,y,x2,y2;
    scanf("%d %d %d %d",&x,&y,&x2,&y2);
    if(x==x2&&y==y2) printf("0");
    else bfs(x-1,y-1,x2-1,y2-1,m,n,k);
}