首页 > 代码库 > POJ1979

POJ1979

Red and Black

好久没敲代码了,试了个简单的DFS题目练练手,这题就是一个DFS模板,一直写下去就行了。

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 char a[21][21];
 5 int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1}, ans, n, m;
 6 bool vis[21][21];
 7 
 8 void dfs(int x, int y){
 9     a[y][x] = #;
10     vis[y][x] = true;
11     ans++;
12     for(int i = 0 ; i < 4; i ++){
13         int xx = x + dx[i], yy = y + dy[i];
14         if(0 <= xx && xx < n && 0 <= yy && yy < m && a[yy][xx] ==. && vis[yy][xx] == false){
15             dfs(xx,yy);
16         }
17     }
18 }
19 
20 int main(){
21     while(cin>>n>>m){
22         if(n==0&&m==0) break;
23         memset(a,0,sizeof(a));
24         memset(vis,false,sizeof(vis));
25         ans = 0;
26         for(int i = 0; i < m; i ++){
27             for(int j = 0; j < n; j ++){
28                 cin >> a[i][j];
29             }
30         }
31 
32         int xx, yy;
33         for(int i = 0; i < m; i ++){
34             for(int j = 0; j < n; j ++){
35                 if(a[i][j] == @){
36                     xx = j; yy = i;
37                     break;
38                 }
39             }
40         }
41         dfs(xx,yy);
42         cout << ans << endl;
43     }
44     return 0;
45 }

 

POJ1979