poj1111 Image Perimeters

题意:给定一个地图,和一个X计算包围给定X的最大的周长。 

 

 1//用栈实现

 2 //简单深搜,边界向四个方向搜索,其他的向8个方向搜索

 3 //周围用‘*’代表省去边界判断 

 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cstdio>
 7 #include<stack>
 8 using namespace std;
 9 const int MAX =100;
10 struct node
11 {
12     int x,y;
13 }st;
14 char map[MAX][MAX];
15 int vis[MAX][MAX];
16 int n,m,a,b,ans;
17 int dx[8]={-1,-1,-1,0,0,1,1,1};
18 int dy[8]={-1,0,1,-1,1,-1,0,1};
19 int da[4]={1,0,-1,0};
20 int db[4]={0,1,0,-1};
21 int dfs(node st)
22 {
23     stack<node> p; node v,vn;
24     vis[st.x][st.y]=1;
25     p.push(st);
26     while(!p.empty())
27     {
28         v=p.top(); p.pop();
29         for(int j=0;j<4;j++)
30         {
31             int aa=v.x+da[j];
32             int bb=v.y+db[j];
33             if(map[aa][bb]==.) ans++;
34         }
35         for(int i=0;i<8;i++)
36         {
37             vn.x=v.x+dx[i];
38             vn.y=v.y+dy[i];
39             if(vn.x>=0&&vn.x<n+2&&vn.y>=0&&vn.y<m+2&&!vis[vn.x][vn.y])
40             {
41                 if(map[vn.x][vn.y]==X) vis[vn.x][vn.y]=1,p.push(vn);
42             }
43         }
44     }
45 }
46 int main()
47 {
48     while(scanf("%d %d %d %d",&n,&m,&a,&b)&&(n||m||a||b))
49     {
50         memset(vis,0,sizeof(vis));
51         for(int i=1;i<=n;i++)
52         {
53             getchar();
54             for(int j=1;j<=m;j++)
55             {
56                 scanf("%c",&map[i][j]);
57             }
58         }
59         for(int i=0;i<=m+1;i++) map[0][i]=map[n+1][i]=.;
60         for(int i=0;i<=n+1;i++) map[i][0]=map[i][m+1]=.;
61         ans=0; st.x=a; st.y=b;
62         dfs(st);
63         printf("%d\n",ans);
64     }
65     return 0;
66 }

poj1111 Image Perimeters

上一篇:django数库库模型参数用法笔记


下一篇:论文学习笔记:Boundary-Aware Cascade Networks for Temporal Action Segmentation