https://codeforces.com/contest/1105/problem/D
C++版本一
题解：
双DFS
先枚举可以走的点
再从这个点出发，DFS在范围si内可以走所有点
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k;
int ans[N],cnt,flag,temp,p;
int a[N];
int vis[N][N];
int b[4][2]={1,0,0,1,-1,0,0,-1};
char str[N][N];
struct node{
int x,y;
int v,id;
}x,f,F,tmp,e[N*N];
queue <node>q;
void bfs(node d){
queue<node>Q;
Q.push(d);
while(!Q.empty()){
F=Q.front();
Q.pop();
if(F.v<=0){
F.v=d.v;
q.push(F);
continue;
}
for(int i=0;i<4;i++){
tmp=F;
tmp.x+=b[i][0];
tmp.y+=b[i][1];
tmp.v--;
if(tmp.x<1||tmp.y<1||tmp.x>n||tmp.y>m){
continue;
}
if(str[tmp.x][tmp.y]=='#'){
continue;
}
if(vis[tmp.x][tmp.y]!=0){
continue;
}//cout<<F.id<<" "<<tmp.x<<" "<<tmp.y<<" "<<tmp.v<<endl;
vis[tmp.x][tmp.y]=F.id;
ans[F.id]++;
Q.push(tmp);
}
}
}
bool cmp(node a,node b){
return a.id<b.id;
}
int main()
{
#ifdef DEBUG
freopen("input5.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%d%d%d",&n,&m,&p);
//scanf("%d",&t);
//while(t--){}
for(int i=1;i<=p;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%s",str[i]+1);
for(int j=1;j<=m;j++){
if(isdigit(str[i][j])){
x.x=i;
x.y=j;
x.v=a[str[i][j]-'0'];
vis[i][j]=1;
x.id=str[i][j]-'0';
ans[str[i][j]-'0']++;
e[++cnt]=x;
//cout<<cnt<<endl;
}
}
}
sort(e+1,e+cnt+1,cmp);
for(int i=1;i<=cnt;i++){
q.push(e[i]);
}
while(!q.empty()){
f=q.front();//cout<<f.id<<endl;
q.pop();
flag=0;
for(int i=0;i<4;i++){
tmp=f;
tmp.x+=b[i][0];
tmp.y+=b[i][1];
if(tmp.x<1||tmp.y<1||tmp.x>n||tmp.y>m){
continue;
}
if(str[tmp.x][tmp.y]=='#'){
continue;
}
if(vis[tmp.x][tmp.y]!=0){
continue;
}//cout<<flag<<" "<<f.id<<" "<<tmp.x<<" "<<tmp.y<<endl;
flag=1;
break;
}
if(flag)
bfs(f);
}
for(int i=1;i<=p;i++){
printf("%d ",ans[i]);
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
#include <bits/stdc++.h>
#define lld I64d
#define mp make_pair
using namespace std ;
/*
inline long long Readin() {
long long K = 0 , F = 1 ; char C = ' ' ;
while( C < '0' or C > '9' ) F = C == '-' ? -1 : 1 , C = getchar() ;
while( C <= '9' and C >= '0' ) K = ( K << 1 ) + ( K << 3 ) + C - '0' , C = getchar() ;
return F * K ;
}
*/
inline int Readin() {
int K = 0 ; char C = ' ' ;
while( C < '0' or C > '9' ) C = getchar() ;
while( C <= '9' and C >= '0' ) K = ( K << 1 ) + ( K << 3 ) + C - '0' , C = getchar() ;
return K ;
}
const int MaxN = 1005 ;
const int x[5] = {0,1,0,0,-1};
const int y[5] = {1,0,1,-1,0};
int N , M , P ;
int Empty , La = 1000000 ;
bool Vis[MaxN][MaxN] ;
int Ans[10] ;
queue< pair<int,int> > Q[10] ;
int S[10] ;
int main() {
scanf( "%d%d%d" , &N , &M , &P ) ;
for(register int i = 1 ; i <= P ; ++i ) scanf( "%d" , &S[i] ) ;getchar();
for(register int i = 1 ; i <= N ; ++i ) {
for(register int j = 1 ; j <= M ; ++j ) {
register char C = getchar() ;
switch( C ) {
case '.' : {
Vis[i][j] = true ;
++Empty ;
break;
}
case '#' : {
break;
}
default : {
register int Pl = C - '0' ;
++Ans[Pl] ;
Q[Pl].push( mp( i , j ));
break;
}
}
}
getchar() ;
//}cout<<"get";
}
while( La != Empty ) {
La= Empty+1; --La;
for(register int i = 1 ; i <= P ; ++i ) {
for(register int Ss = 1 ; Ss <= S[i] and 0<Q[i].size() ; ++Ss){
register int End = Q[i].size() ;
while( End-- ) {
register int Hang = Q[i].front().first;
register int Lie = Q[i].front().second;
Q[i].pop();
for(register int ii = 0 ; ++ii < 5 ; ) {
int th = Hang + x[ii] ,tl=Lie+y[ii];
if(th<1 or tl<1 or th>N or tl > M or false and true)continue;
if( Vis[th][tl] ) { --Empty;
++Ans[i] ;
Q[i].push(mp(th,tl) ) ;
Vis[th][tl] = not true ;
}
}
}
}
}
}
for(register int i = 0 ; ++i <= P ; printf( "%d " , Ans[i])) ;
return not printf( "\n") ;
} C++版本三
#include <bits/stdc++.h>
using namespace std;
const int dr[] = {1,-1,0,0};
const int dc[] = {0,0,1,-1};
const int maxn = 1000+5;
typedef pair<int,int> pii;
int n,m,p,s[maxn];
int mp[maxn][maxn];
int ans[15];
vector<pii> v[15];
bool bfs(int x) {
vector<pii> que;
int tz = v[x].size();
que.resize(tz);
for(int i = 0; i < v[x].size(); ++i) {
que[i] = v[x][i];
}
v[x].clear();
for(int i = 0; i < que.size(); ++i) {
for(int j = 0; j < 4; ++j) {
pii u = que[i];
int nx = u.first+dr[j], ny = u.second+dc[j];
// cout << nx <<" " << ny << endl;
if(nx < 0 || nx >= n || ny < 0 || ny >= m || mp[nx][ny] != 0)
continue;
mp[nx][ny] = x;
ans[x]++;
v[x].push_back(pii(nx,ny));
}
}
if(v[x].size() == 0)
return 0;
return 1;
}
void print() {
for(int i = 1; i <= p; ++i) {
cout << ans[i] <<" ";
}
}
int main() {
scanf("%d%d%d", &n, &m, &p);
for(int i = 1; i <= p; ++i)
scanf("%d", &s[i]);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j){
char ch;
scanf(" %c", &ch);
if(ch == '.')
mp[i][j] = 0;
else if(ch == '#')
mp[i][j] = -1;
else {
mp[i][j] = ch-'0';
v[mp[i][j]].push_back(pii(i,j));
ans[mp[i][j]]++;
}
}
}
while(1){
bool flag = false;
for(int i = 1; i <= p; ++i) {
for(int j = 0; j < s[i]; ++j) {
bool flag2 = bfs(i);
flag |= flag2;
if(flag2 == false)
break;
}
}
if(flag == false)
break;
} for(int i = 0; i < n; ++i,cout<<endl)
for(int j = 0; j < m; ++j) {
cout << mp[i][j];
}
print();
return 0;
}
京公网安备 11010502036488号