首页 > 代码库 > 【宽搜】ECNA 2015 D Rings (Codeforces GYM 100825)
【宽搜】ECNA 2015 D Rings (Codeforces GYM 100825)
题目链接：
http://codeforces.com/gym/100825
题目大意：
给你一张N*N(N<=100)的图表示一个树桩，‘T‘为年轮，‘.‘为空，求每个‘T‘属于哪一圈年轮，空的为‘.‘，如果最内圈<10，每个格子用两位表示，否则用三位，不足的用‘.‘补足。
题目思路：
【宽搜】
初始所有点标记为INF，先将图上所有的‘.‘标记为0，边缘如果有‘T‘记为1，并把‘.‘和边缘所有的点加入队列，接下来一个一个上下左右扩展并更新答案，没进队的进队。最后输出。
1 // 2 //by coolxxx 3 //#include<bits/stdc++.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<string> 7 #include<iomanip> 8 #include<map> 9 #include<stack> 10 #include<queue> 11 #include<set> 12 #include<bitset> 13 #include<memory.h> 14 #include<time.h> 15 #include<stdio.h> 16 #include<stdlib.h> 17 #include<string.h> 18 //#include<stdbool.h> 19 #include<math.h> 20 #define min(a,b) ((a)<(b)?(a):(b)) 21 #define max(a,b) ((a)>(b)?(a):(b)) 22 #define abs(a) ((a)>0?(a):(-(a))) 23 #define lowbit(a) (a&(-a)) 24 #define sqr(a) ((a)*(a)) 25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b)) 26 #define mem(a,b) memset(a,b,sizeof(a)) 27 #define eps (1e-10) 28 #define J 10000 29 #define mod 1000000007 30 #define MAX 0x7f7f7f7f 31 #define PI 3.14159265358979323 32 #pragma comment(linker,"/STACK:1024000000,1024000000") 33 #define N 104 34 #define M 10004 35 using namespace std; 36 typedef long long LL; 37 double anss; 38 LL aans; 39 int cas,cass; 40 int n,m,lll,ans; 41 int q[M][2]; 42 int a[N][N]; 43 bool u[N][N]; 44 char s[N][N]; 45 void spfa() 46 { 47 int x,y,l=0,r=cas; 48 while(l!=r) 49 { 50 x=q[l=(l+1)%M][0],y=q[l][1]; 51 cass=max(cass,a[x][y]); 52 u[x][y]=0; 53 if(x+1<=n && a[x+1][y]>a[x][y]+1) 54 { 55 q[r=(r+1)%M][0]=x+1,q[r][1]=y; 56 u[x+1][y]=1; 57 a[x+1][y]=a[x][y]+1; 58 } 59 if(y+1<=m && a[x][y+1]>a[x][y]+1) 60 { 61 q[r=(r+1)%M][0]=x,q[r][1]=y+1; 62 u[x][y+1]=1; 63 a[x][y+1]=a[x][y]+1; 64 } 65 if(x-1>0 && a[x-1][y]>a[x][y]+1) 66 { 67 q[r=(r+1)%M][0]=x-1,q[r][1]=y; 68 u[x-1][y]=1; 69 a[x-1][y]=a[x][y]+1; 70 } 71 if(y-1>0 && a[x][y-1]>a[x][y]+1) 72 { 73 q[r=(r+1)%M][0]=x,q[r][1]=y-1; 74 u[x][y-1]=1; 75 a[x][y-1]=a[x][y]+1; 76 } 77 } 78 } 79 int main() 80 { 81 #ifndef ONLINE_JUDGE 82 // freopen("1.txt","r",stdin); 83 // freopen("2.txt","w",stdout); 84 #endif 85 int i,j,k; 86 int x,y,z; 87 // init(); 88 // for(scanf("%d",&cass);cass;cass--) 89 // for(scanf("%d",&cas),cass=1;cass<=cas;cass++) 90 // while(~scanf("%s",s)) 91 while(~scanf("%d",&n)) 92 { 93 cas=0;cass=0;mem(u,0);mem(a,MAX); 94 scanf("%d",&m); 95 for(i=1;i<=n;i++) 96 { 97 scanf("%s",s[i]+1); 98 for(j=1;j<=m;j++) 99 {100 if(s[i][j]==‘.‘)101 {102 q[++cas][0]=i,q[cas][1]=j;103 a[i][j]=0;104 }105 else if(i==1 || i==n || j==1 || j==m)106 {107 q[++cas][0]=i,q[cas][1]=j;108 a[i][j]=1;109 }110 }111 }112 spfa();113 /*114 for(i=1;i<=n;i++)115 {116 for(j=1;j<=m;j++)117 printf("%d ",a[i][j]);118 puts("");119 }120 */121 if(cass<10)122 {123 for(i=1;i<=n;i++)124 {125 for(j=1;j<=m;j++)126 {127 printf(".");128 if(a[i][j]==0)printf(".");129 else printf("%d",a[i][j]);130 }131 puts("");132 }133 }134 else135 {136 for(i=1;i<=n;i++)137 {138 for(j=1;j<=m;j++)139 {140 printf(".");141 if(a[i][j]==0)printf("..");142 else if(a[i][j]<10)printf(".%d",a[i][j]);143 else printf("%d",a[i][j]);144 }145 puts("");146 }147 }148 149 }150 return 0;151 }152 /*153 //154 155 //156 */
【宽搜】ECNA 2015 D Rings (Codeforces GYM 100825)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。