HDU_2612_(BFS)

HDU 2612

思路:
  • 记录出发点(Y和 M)到每一个kfc的距离,
  • 更新ans最小距离之和
    坑点:
  1. 不能走对方的出发点,
  2. 更新ans时注意 有的kfc被包围了,不能走到,除去dist[][] == 0的情况
  3. 清空数组的细节问题
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    #include <iostream>
    #include <string.h>
    #include <queue>

    using namespace std;

    const int maxn = 201;

    int n,m;
    char grid[maxn][maxn];
    int next1[4][2] = {0,1,1,0,0,-1,-1,0};
    bool vis[maxn][maxn];
    int disty[maxn][maxn];
    int distm[maxn][maxn];
    long long ans;

    struct node {
    	int x,y;
    	int step;
    	node(){}
    	node(int a,int b,int c) {
    		x = a; y = b; step = c;
    	}
    };

    void bfs(int x,int y,char source) {
    	memset(vis,0,sizeof vis);
    	queue<node> que;
    	
    	vis[x][y] = 1;
    	que.push( node(x,y,0) );	
    		
    	while( !que.empty() ) {
    		node cur = que.front();
    		que.pop();

    		for (int i=0; i<4; i++) {
    			int tx = cur.x + next1[i][0];
    			int ty = cur.y + next1[i][1];
    			if (tx<1 || ty<1 || tx>n || ty>m) continue;
    			if (grid[tx][ty] == '#' || grid[tx][ty] == 'Y' || grid[tx][ty] == 'M') continue;
    			if ( !vis[tx][ty] ) {
    				vis[tx][ty] = 1;
    				if (grid[tx][ty] == '@') {
    					if (source == 'Y') {
    						disty[tx][ty] = cur.step+1;
    					}
    					else {
    						distm[tx][ty] = cur.step+1; 
    					}
    					que.push({tx,ty,cur.step+1});
    				}
    				else if (grid[tx][ty] == '.') {
    					que.push({tx,ty,cur.step+1});
    				}
    			}
    		}
    	}
    	return ;
    }

    void init() {
    	ans = 0x7fffffff;
    	memset(vis,0,sizeof vis);
    	memset(grid,0,sizeof grid);
    	memset(distm,0,sizeof distm);
    	memset(disty,0,sizeof disty);
    }

    int main() {
    //	freopen("a.txt","r",stdin);
    	while (scanf("%d%d",&n,&m) != EOF) {
    		init();
    		int Y_x,Y_y,M_x,M_y;
    		for (int i=1; i<=n; i++)
    			for (int j=1; j<=m; j++) {
    				cin >> grid[i][j];
    				if (grid[i][j] == 'Y') {
    					Y_x = i; Y_y = j;
    				}
    				else if (grid[i][j] == 'M') {
    					M_x = i; M_y = j;
    				}
    			}

    		// 从两个起点分别bfs，记录kfc的距离
    		
    		bfs(Y_x,Y_y,'Y');
    		bfs(M_x,M_y,'M');
    	
    		for (int i=1; i<=n; i++) 
    			for (int j=1; j<=m; j++) {
    				if (grid[i][j] == '@' && (distm[i][j] != 0 && disty[i][j] != 0) ) {
    					// 更新结果
    					if (distm[i][j] + disty[i][j] < ans) 
    						ans = (distm[i][j] + disty[i][j]);
    				}
    			}
    		cout << ans*11 << endl;
    	}
    	return 0;
    }
算法
BFS

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！