[1443] Weiqi

[1443] Weiqi
http://ac.nbutoj.com/Problem/view.xhtml?id=1443
时间限制: 1000 ms　内存限制: 65535 K
问题描述
Have you ever played Weiqi?
In a composition, there exist two kinds of chess pieces black and white.
The problem is so easy, can you find out how many white pieces are encircled by blacks?
输入
First line will contain two integers M and N (3 <= M, N <= 100), means the size of the composition.
Then M lines, each line N integers only including '1', '2', and '0' ('1' represent black piece, '2' represent white piece and '0' represent empty).
输出
Print how many white pieces are encircled by black.
样例输入

样例输出
```
1
0
```
提示
```
详情看样例输入输出
```
来源
```
Hungar
```
操作

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

char map[110][110];
int vis[110][110];

int m,n,flag,tag;

int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

int cnt;

void DFS(int x,int y){
    for(int i=0;i<4;i++){
        int sx=x+dir[i][0];
        int sy=y+dir[i][1];
        if(sx<0 || sx>=m || sy<0 || sy>=n || map[sx][sy]=='1')
            continue;
        if(map[sx][sy]=='0' || sx==0 || sx==m-1 || sy==0 || sy==n-1)
            tag=1;
        //printf("22222\n");
        //printf("x=%d y=%d\n",x,y);
        //printf("sx=%d sy=%d\n",sx,sy);
        //printf("------- cnt=%d\n",cnt);
        if(!vis[sx][sy]){
            vis[sx][sy]=1;
            cnt++;
            DFS(sx,sy);
        }
    }
}

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d%d",&m,&n)){
        getchar();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++)
                scanf("%c",&map[i][j]);
            getchar();
        }
        memset(vis,0,sizeof(vis));
        int ans=0;
        for(int i=1;i<m-1;i++)
            for(int j=1;j<n-1;j++){
                if(map[i][j]=='2' && !vis[i][j]){
                    //printf("i=%d j=%d\n",i,j);
                    vis[i][j]=1;
                    cnt=1;
                    tag=0;
                    DFS(i,j);
                    //printf("cnt=%d\n",cnt);
                    if(!tag)
                        ans+=cnt;
                }
            }
        printf("%d\n",ans);
    }
    return 0;
}