hdoj 1312 Red and Black【bfs】

左手的ㄟ右手 2022-08-10 06:19 9阅读 0赞

# Red and Black #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 13953    Accepted Submission(s): 8644**  
dfs做法，参见[http://blog.csdn.net/nailnehc/article/details/48007321][http_blog.csdn.net_nailnehc_article_details_48007321]

题目大意；给一个n\*m的矩阵，[‘@’][Link 1]为你当前站的位置，在矩阵中，‘ . ’表示可行走，‘ \# ’表示不可行走，问从当前位置出发，能走到的格子有多少个【只能上下左右移动】；

已Accept代码【c++提交】

#include <cstdio>
    #include <queue>
    using namespace std;
    char map[22][22];
    int m, n;
    int r, c;
    
    int dx[] = {0, 0, 1, -1};
    int dy[] = {-1, 1, 0, 0};
    typedef struct node {
    	int x, y;
    }node;
    
    queue <node> Q;
    void BFS() {
    	while(!Q.empty())
    		Q.pop();
    	node cur;
    	cur.x = r;
    	cur.y = c;
    	Q.push(cur);
    	int total = 1;
    	map[cur.x][cur.y] = '#';
    	while(!Q.empty()) {
    		node tmp;
    		tmp = Q.front();
    		Q.pop();
    		for(int i = 0; i < 4; i++) {
    			int x = tmp.x + dx[i];
    			int y = tmp.y + dy[i];
    			if(x < 1 || x > n || y < 1 || y > m || map[x][y] == '#')
    				continue;
    			else {
    				cur.x = x;
    				cur.y = y;
    				Q.push(cur);
    				map[x][y] = '#';
    				total++;
    			}
    		}
    	}
    	printf("%d\n", total);
    }
    
    int main() {
    	while(scanf("%d%d", &m, &n), n | m) {
    		for(int i = 1; i <= n; i++) {
    			getchar();
    			for(int j = 1; j <= m; j++) {
    				scanf("%c", &map[i][j]);
    				if(map[i][j] == '@') {
    					r = i;
    					c = j;
    				}
    			}
    		}
    		BFS();
    	}
    	return 0;
    }

[http_blog.csdn.net_nailnehc_article_details_48007321]: http://blog.csdn.net/nailnehc/article/details/48007321
[Link 1]: mailto:‘@’