NC24105. [USACO 2017 Ope B]Modern Art
描述
Picowso paints in a very particular way. She starts with an N×N blank canvas, represented by an N×N grid of zeros, where a zero indicates an empty cell of the canvas. She then draws 9 rectangles on the canvas, one in each of 9 colors (conveniently numbered 1…9). For example, she might start by painting a rectangle in color 2, giving this intermediate canvas:
2220 2220 2220 0000
She might then paint a rectangle in color 7:
2220 2777 2777 0000
And then she might paint a small rectangle in color 3:
2230 2737 2777 0000
Each rectangle has sides parallel to the edges of the canvas, and a rectangle could be as large as the entire canvas or as small as a single cell. Each color from 1…9 is used exactly once, although later colors might completely cover up some of the earlier colors.
Given the final state of the canvas, please count how many of the colors still visible on the canvas could have possibly been the first to be painted.
输入描述
The first line of input contains N, the size of the canvas (1≤N≤10). The next N lines describe the final picture of the canvas, each containing N numbers that are in the range 0…9. The input is guaranteed to have been drawn as described above, by painting successive rectangles in different colors.
输出描述
Please output a count of the number of colors that could have been drawn first, from among all colors visible in the final canvas.
示例1
输入:
4 2230 2737 2777 0000
输出:
1
说明:
In this example, only color 2 could have been the first to be painted. Color 3 clearly had to have been painted after color 7, and color 7 clearly had to have been painted after color 2.C(clang11) 解法, 执行用时: 2ms, 内存消耗: 372K, 提交时间: 2020-11-07 12:21:40
#include<stdio.h>
int up[10],down[10],left[10],right[10];
int tag[10];
char s[100][100];
int main()
{
int n;
scanf("%d",&n);
int i,j,k;
for(i=1;i<=n;i++)
scanf("%s",s[i]+1);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(tag[s[i][j]-'0']==0)
{
up[s[i][j]-'0']=down[s[i][j]-'0']=i;
left[s[i][j]-'0']=right[s[i][j]-'0']=j;
tag[s[i][j]-'0']=1;
continue;
}
if(up[s[i][j]-'0']>i)
up[s[i][j]-'0']=i;
if(down[s[i][j]-'0']<i)
down[s[i][j]-'0']=i;
if(left[s[i][j]-'0']>j)
left[s[i][j]-'0']=j;
if(right[s[i][j]-'0']<j)
right[s[i][j]-'0']=j;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=9;k++)
{
if(k==s[i][j]-'0')
continue;
if(tag[k]==0)
continue;
if(left[k]<=j&&right[k]>=j&&up[k]<=i&&down[k]>=i)
tag[s[i][j]-'0']=2;
}
int sum=0;
for(i=1;i<=9;i++)
if(tag[i]==1)
sum++;
printf("%d",sum);
}
Python3(3.9) 解法, 执行用时: 19ms, 内存消耗: 2808K, 提交时间: 2020-11-09 12:19:32
n = int(input())
canvas = [[] for i in range(n)]
ans = 0
color_dict = {}
for i in range(n):
s = input()
for c in s:
canvas[i].append(int(c))
for i in range(n):
for j in range(n):
if canvas[i][j] != 0:
if canvas[i][j] not in color_dict.keys():
color_dict[canvas[i][j]] = {'left': j, 'right': j, 'up': i, 'down': i}
else:
if j < color_dict[canvas[i][j]]['left']:
color_dict[canvas[i][j]]['left'] = j
if j > color_dict[canvas[i][j]]['right']:
color_dict[canvas[i][j]]['right'] = j
if i > color_dict[canvas[i][j]]['down']:
color_dict[canvas[i][j]]['down'] = i
pos_color = list(color_dict.keys())
remove_set = set()
for color in pos_color:
left = color_dict[color]['left']
right = color_dict[color]['right']
up = color_dict[color]['up']
down = color_dict[color]['down']
for i in range(up, down + 1):
for j in range(left, right + 1):
if canvas[i][j] != color:
remove_set.add(canvas[i][j])
print(len(pos_color) - len(remove_set))
C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2020-11-10 13:36:53
#include<bits/stdc++.h>
using namespace std;
int n;
int l[2][10],r[2][10],mp[20][20],in[10],vis[10];
int main()
{
scanf("%d",&n);
memset(l[1],0x3f,sizeof(l[1]));
memset(r[1],0x3f,sizeof(r[1]));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int x;
scanf("%1d",&x);
mp[i][j]=x;
vis[x]=1;
l[1][x]=min(l[1][x],i);
r[1][x]=min(r[1][x],j);
l[2][x]=max(l[2][x],i);
r[2][x]=max(r[2][x],j);
}
}
for(int i=1;i<=9;i++)
{
if(!vis[i])
continue;
for(int j=l[1][i];j<=l[2][i];j++)
{
for(int k=r[1][i];k<=r[2][i];k++)
{
if(mp[j][k]!=i)
in[mp[j][k]]=1;
}
}
}
int ans=0;
for(int i=1;i<=9;i++)
if(vis[i]&&!in[i])
ans++;
printf("%d",ans);
return 0;
}