題意：給一個n*m(<=100)的圖，圖中0表示臺燈，1表示空地，以臺燈和墻作為邊界，問能否使用k種使得聯通的線段上沒有重復的顏色

分析：只要連續的空地不超過k個就必然存在一個解，可以選擇如下構造，假設n=5,m=5,k=3

1 2 3 1 2

2 3 1 2 3

3 1 2 3 1

1 2 3 1 2

2 3 1 2 3

這樣，把燈的位置都換為0，如果檢測到沒有連續的超過k的線段，那么這就是一個可行解

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e2+5; 4 int g[maxn][maxn],res[maxn][maxn]; 5 int t,n,m,k; 6 7 void init(){ 8 for(int i=1;i<=n;i++){ 9 res[i][1]=(res[i-1][1]+1)%k; 10 for(int j=2;j<=m;j++)res[i][j]=(res[i][j-1]+1)%k; 11 } 12 } 13 14 void print(int x,int y){ 15 if(!g[x][y])cout<<0; 16 else cout<<res[x][y]+1; 17 } 18 19 int main(){ 20 int t;cin>>t; 21 while(t--){ 22 cin>>n>>m>>k;init(); 23 24 for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){ 25 cin>>g[i][j]; 26 if(!g[i][j])res[i][j]=0; 27 } 28 29 bool flag=1; 30 31 for(int i=1;i<=n;i++){ 32 int j=1; 33 for(;j<=m;j++){ 34 int cnt=0; 35 while(j<=m&&g[i][j])cnt++,j++; 36 if(cnt>k){flag=0;break;} 37 } 38 } 39 40 for(int i=1;i<=m;i++){ 41 int j=1; 42 for(;j<=n;j++){ 43 int cnt=0; 44 while(j<=n&&g[j][i])cnt++,j++; 45 if(cnt>k){flag=0;break;} 46 } 47 } 48 if(!flag){puts("NO");continue;} 49 puts("YES"); 50 51 for(int i=1;i<=n;i++){ 52 print(i,1); 53 for(int j=2;j<=m;j++)cout<<" ",print(i,j); 54 cout<<endl; 55 } 56 } 57 return 0; 58 }

?

轉載于:https://www.cnblogs.com/jihe/p/6673240.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的RCC 2017 Qual 1 Mail.Ru, April 2, 2017 Problem B. Painting the Wall的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。