g596. 2. 動線安排

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}')

相關文章