2023.1.25 PM 08:30 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=g596 出題者 : 2021年11月APCS 標籤 : 模擬法 難易度 : 2
解題想法 : 此題是個十分麻煩的模擬題,但若將牽線和拆線定義成函式,再加上實際將場館印出來,就能夠增加debug的效率。 實作上可以像下方C/C++的Code只定義拆線牽線兩個函式,也可以像Python的Code將四個方向都分開定義,會更好除錯。 此題的程式碼相當冗長,但不會出現太困難的語法,跑起來也相當快,細心的模擬就可以AC了。
//C language
// _ = 空 , | = 直線 , - = 橫線 , @ = 木樁 , # = 兩線相交
#include <stdio.h>
int m,n;
char exh[100][100]={};
int lead(int x,int y){
int cur_area=0;
int i,j;
char now;
for(i=y-1;i>=0;i--){
now = exh[x][i];
if(now=='-')break;
else if(now=='@'){
for(j=i+1;j<y;j++){
now = exh[x][j];
if(now=='\0'){
exh[x][j]='-';
cur_area++;
}
else if(now=='|')exh[x][j]='#';
}
break;
}
}
for(i=x-1;i>=0;i--){
now = exh[i][y];
if(now=='|')break;
else if(now=='@'){
for(j=i+1;j<x;j++){
now = exh[j][y];
if(now=='\0'){
exh[j][y] = '|';
cur_area++;
}
else if(now=='-')exh[j][y] = '#';
}
break;
}
}
for(i=y+1;i<n;i++){
now = exh[x][i];
if(now=='-')break;
else if(now=='@'){
for(j=i-1;j>y;j--){
now = exh[x][j];
if(now=='\0'){
exh[x][j] = '-';
cur_area++;
}
else if(now=='|')exh[x][j] = '#';
}
break;
}
}
for(i=x+1;i<m;i++){
now = exh[i][y];
if(now=='|')break;
else if(now=='@'){
for(j=i-1;j>x;j--){
now = exh[j][y];
if(now=='\0'){
exh[j][y] = '|';
cur_area++;
}
else if(now=='-')exh[j][y] = '#';
}
break;
}
}
return cur_area;
}
int tear(int x,int y){
int i,j,cur_area=0;
char now;
for(i=y-1;i>=0;i--){
now = exh[x][i];
if(now=='@'){
for(j=i+1;j<y;j++){
now = exh[x][j];
if(now=='-'){
exh[x][j]='\0';
cur_area--;
}
else if(now=='#'){
exh[x][j]='|';
}
}
break;
}
}
for(i=y+1;i<n;i++){
now = exh[x][i];
if(now=='@'){
for(j=i-1;j>y;j--){
now = exh[x][j];
if(now=='-'){
exh[x][j]='\0';
cur_area--;
}
else if(now=='#'){
exh[x][j]='|';
}
}
break;
}
}
for(i=x-1;i>=0;i--){
now = exh[i][y];
if(now=='@'){
for(j=i+1;j<x;j++){
now = exh[j][y];
if(now=='|'){
exh[j][y]='\0';
cur_area--;
}
else if(now=='#'){
exh[j][y]='-';
}
}
break;
}
}
for(i=x+1;i<m;i++){
now = exh[i][y];
if(now=='@'){
for(j=i-1;j>x;j--){
now = exh[j][y];
if(now=='|'){
exh[j][y]='\0';
cur_area--;
}
else if(now=='#'){
exh[j][y]='-';
}
}
break;
}
}
return cur_area;
}
int main()
{
int h,max_area=0,cur_area=0;
scanf("%d%d%d",&m,&n,&h);
while(h--){
int x,y,t;
scanf("%d%d%d",&x,&y,&t);
if(t==0){
if(exh[x][y]=='-' || exh[x][y]=='|'){
cur_area+=tear(x,y);
cur_area+=lead(x,y);
}
else if(exh[x][y]=='\0'){
cur_area++;
cur_area+=lead(x,y);
}
exh[x][y]='@';
}
else if(t==1){
exh[x][y]='\0';
cur_area--;
cur_area+=tear(x,y);
}
if(cur_area>max_area)max_area=cur_area;
}
printf("%d\n",max_area);
printf("%d\n",cur_area);
return 0;
}

//C++ language
// _ = 空 , | = 直線 , - = 橫線 , @ = 木樁 , # = 兩線相交
#include<iostream>
using namespace std;
int m,n;
char exh[100][100]={};
int lead(int x,int y){
int cur_area=0;
int i,j;
char now;
for(i=y-1;i>=0;i--){
now = exh[x][i];
if(now=='-')break;
else if(now=='@'){
for(j=i+1;j<y;j++){
now = exh[x][j];
if(now=='\0'){
exh[x][j]='-';
cur_area++;
}
else if(now=='|')exh[x][j]='#';
}
break;
}
}
for(i=x-1;i>=0;i--){
now = exh[i][y];
if(now=='|')break;
else if(now=='@'){
for(j=i+1;j<x;j++){
now = exh[j][y];
if(now=='\0'){
exh[j][y] = '|';
cur_area++;
}
else if(now=='-')exh[j][y] = '#';
}
break;
}
}
for(i=y+1;i<n;i++){
now = exh[x][i];
if(now=='-')break;
else if(now=='@'){
for(j=i-1;j>y;j--){
now = exh[x][j];
if(now=='\0'){
exh[x][j] = '-';
cur_area++;
}
else if(now=='|')exh[x][j] = '#';
}
break;
}
}
for(i=x+1;i<m;i++){
now = exh[i][y];
if(now=='|')break;
else if(now=='@'){
for(j=i-1;j>x;j--){
now = exh[j][y];
if(now=='\0'){
exh[j][y] = '|';
cur_area++;
}
else if(now=='-')exh[j][y] = '#';
}
break;
}
}
return cur_area;
}
int tear(int x,int y){
int i,j,cur_area=0;
char now;
for(i=y-1;i>=0;i--){
now = exh[x][i];
if(now=='@'){
for(j=i+1;j<y;j++){
now = exh[x][j];
if(now=='-'){
exh[x][j]='\0';
cur_area--;
}
else if(now=='#'){
exh[x][j]='|';
}
}
break;
}
}
for(i=y+1;i<n;i++){
now = exh[x][i];
if(now=='@'){
for(j=i-1;j>y;j--){
now = exh[x][j];
if(now=='-'){
exh[x][j]='\0';
cur_area--;
}
else if(now=='#'){
exh[x][j]='|';
}
}
break;
}
}
for(i=x-1;i>=0;i--){
now = exh[i][y];
if(now=='@'){
for(j=i+1;j<x;j++){
now = exh[j][y];
if(now=='|'){
exh[j][y]='\0';
cur_area--;
}
else if(now=='#'){
exh[j][y]='-';
}
}
break;
}
}
for(i=x+1;i<m;i++){
now = exh[i][y];
if(now=='@'){
for(j=i-1;j>x;j--){
now = exh[j][y];
if(now=='|'){
exh[j][y]='\0';
cur_area--;
}
else if(now=='#'){
exh[j][y]='-';
}
}
break;
}
}
return cur_area;
}
int main()
{
int h,max_area=0,cur_area=0;
cin>>m>>n>>h;
while(h--){
int x,y,t; cin>>x>>y>>t;
if(t==0){
if(exh[x][y]=='-' || exh[x][y]=='|'){
cur_area+=tear(x,y);
cur_area+=lead(x,y);
}
else if(exh[x][y]=='\0'){
cur_area++;
cur_area+=lead(x,y);
}
exh[x][y]='@';
}
else if(t==1){
exh[x][y]='\0';
cur_area--;
cur_area+=tear(x,y);
}
if(cur_area>max_area)max_area=cur_area;
}
cout<<max_area<<"\n"<<cur_area<<"\n";
return 0;
}

## Python language
## _ = 空 , | = 直線 , - = 橫線 , @ = 木樁 , # = 兩線相交
m,n,h=map(int,input().split())
Map=[['_']*n for _ in range(m)]
def lead_up(x,y):
area=0
success=False
for i in range(x-1,-1,-1):
if Map[i][y]=='@':
success=True
break
elif Map[i][y]=='-': Map[i][y]='#'
elif Map[i][y]=='_':
area+=1
Map[i][y]='|'
if not success: area+=tear_down(-1,y)
return area
def lead_down(x,y):
area=0
success=False
for i in range(x+1,m):
if Map[i][y]=='@':
success=True
break
elif Map[i][y]=='-': Map[i][y]='#'
elif Map[i][y]=='_':
area+=1
Map[i][y]='|'
if not success: area+=tear_up(m,y)
return area
def lead_right(x,y):
area=0
success=False
for i in range(y+1,n):
if Map[x][i]=='@':
success=True
break
elif Map[x][i]=='|': Map[x][i]='#'
elif Map[x][i]=='_':
area+=1
Map[x][i]='-'
if not success: area+=tear_left(x,n)
return area
def lead_left(x,y):
area=0
success=False
for i in range(y-1,-1,-1):
if Map[x][i]=='@':
success=True
break
elif Map[x][i]=='|': Map[x][i]='#'
elif Map[x][i]=='_':
area+=1
Map[x][i]='-'
if not success: area+=tear_right(x,-1)
return area
def lead_all(x,y): return lead_up(x,y)+lead_down(x,y)+lead_right(x,y)+lead_left(x,y)
def tear_up(x,y):
area=0
for i in range(x-1,-1,-1):
if Map[i][y]=='@': break
elif Map[i][y]=='#': Map[i][y]='-'
elif Map[i][y]=='|':
area-=1
Map[i][y]='_'
return area
def tear_down(x,y):
area=0
for i in range(x+1,m):
if Map[i][y]=='@': break
elif Map[i][y]=='#': Map[i][y]='-'
elif Map[i][y]=='|':
area-=1
Map[i][y]='_'
return area
def tear_right(x,y):
area=0
for i in range(y+1,n):
if Map[x][i]=='@': break
elif Map[x][i]=='#': Map[x][i]='|'
elif Map[x][i]=='-':
area-=1
Map[x][i]='_'
return area
def tear_left(x,y):
area=0
for i in range(y-1,-1,-1):
if Map[x][i]=='@': break
elif Map[x][i]=='#': Map[x][i]='|'
elif Map[x][i]=='-':
area-=1
Map[x][i]='_'
return area
def tear_all(x,y): return tear_up(x,y)+tear_down(x,y)+tear_right(x,y)+tear_left(x,y)
operates=[]
for i in range(h): operates.append([int(x) for x in input().split()])
max_area=cur_area=0
for i in operates:
x,y,t=i
now=Map[x][y]
if t==0: # add
Map[x][y]='@'
if now=='_': cur_area+=lead_all(x,y)+1
elif now=='#': continue
elif now=='-': cur_area+=lead_up(x,y)+lead_down(x,y)
elif now=='|': cur_area+=lead_left(x,y)+lead_right(x,y)
elif t==1: #remove
Map[x][y]='_'
cur_area+=tear_all(x,y)-1
max_area=max(max_area,cur_area)
print(f'{max_area}\n{cur_area}')
