1 条题解

  • 0
    @ 2024-11-3 21:25:48

    std:

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1009;
    struct Box{
        int l,r,u,d;
    };
    Box b[N*N];
    char mp[N][N];
    int id[N][N];
    int n,m;
    void getBox(int x,int y,int idx){
        int i=x,j=y;
        while(mp[i][j]!='|') j--; 
    	b[idx].l=j;
        j=y;
        while(mp[i][j]!='|') j++; 
    	b[idx].r=j;
        j=y;
        while(mp[i][j]!='-') i--; 
    	b[idx].u=i;
        i=x;
        while(mp[i][j]!='-') i++; 
    	b[idx].d=i;
        for(j=b[idx].l;j<=b[idx].r;j++) 
    		id[b[idx].u][j]=idx;
    }
    #define UP 1
    #define DOWN 2
    #define LEFT 3
    #define RIGHT 4
    int pipeToBox(int x,int y,int dir){
        while(!id[x][y]){
            if(mp[x][y]=='|'){
                x++;
                continue;
            }
            if(mp[x][y]=='-') {
            	if(dir==LEFT) y--;
                else y++;
                continue;
            }
            if(dir==LEFT || dir==RIGHT){
                x++,dir=DOWN;
                continue; 
            }        
            if(y>1 && mp[x][y-1]=='-') y--,dir=LEFT;
            else y++,dir=RIGHT;
        }
        return id[x][y];
    }
    void dfs(int u){
        for(int i=b[u].d;i>=b[u].u;i--){				//从下往上枚举水面高度 
            int v=0;
            if(b[u].l>1 && mp[i][b[u].l-1]=='-') 		//左侧有管道 
    			v=pipeToBox(i,b[u].l-1,LEFT);				
            if(b[u].r<m && mp[i][b[u].r+1]=='-') 		//右侧有管道 
    			v=pipeToBox(i,b[u].r+1,RIGHT);
            if(v) dfs(v);
        }
        printf("%d\n",u);
    }
    bool isDigit(char ch){
    	return '0'<=ch&&ch<='9';
    }
    int main(){
    	//freopen("flowchart.in","r",stdin);
    	//freopen("flowchart.out","w",stdout);
        scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if(!isDigit(mp[i][j])) continue;
                int id=mp[i][j]-'0';
                while(j+1<m && isDigit(mp[i][j+1])) 
    				id=id*10+mp[i][++j]-'0';
                getBox(i,j,id);
            }    
        dfs(1);
    	return 0;
    } 
    
    

    信息

    ID
    3
    时间
    1000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    2
    已通过
    1
    上传者