欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

jzoj5769 引子

程序员文章站 2022-06-12 13:34:48
...

jzoj5769 引子
jzoj5769 引子
jzoj5769 引子

链接(需要jzoj账号)

  • 这道题是一道比较简单的模拟,重点是我们需要判断水箱与水管,一种方法是建树,当然我们这种怕麻烦的就只会直接搜索了
  • 我们先将整张图输入,然后可以离线处理,每当处理到数字时我们便查找一下数字,并将整个水箱全部染色,然后处理完之后我们对1水箱处理,然后判断水箱两边的水管,由水管找到下个水箱,并接着处理,注意输出顺序即可。
  • 代码:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m;
struct Node{
    char data;
    int which;
    bool is;
}a[1005][1005];
struct Case{
    int xs,xe,
        ys,ye;
}b[2505];
void Down(int x,int y,int  num){//找到水箱的右下点
    int x0=x;
    int y0=y;
    while(a[x0][y0].data!='-') x0++;
    while(a[x0][y0].data!='+') y0++;
    b[num].ye=y0;
    b[num].xe=x0;
    return;
}

void Up(int x,int y,int num){//找到水箱的左上点
    int x0=x;
    int y0=y;
    while(a[x0][y0].data!='-') x0--;
    while(a[x0][y0].data!='+') y0--;
    b[num].xs=x0;
    b[num].ys=y0;
    return;
}

void Search(int x,int y,int num){ //查找水箱并染色
    Up(x,y,num);
    Down(x,y,num);
    for(int i=b[num].xs;i<=b[num].xe;i++)
        for(int j=b[num].ys;j<=b[num].ye;j++)
            a[i][j].which=num,a[i][j].is=1;
    return;
}

int To(int x,int y){   //对水管的处理,分了几种情况
    if(a[x][y].which!=-1) return a[x][y].which;
    a[x][y].is=1;
    if(a[x][y].data=='-'){
        if(a[x][y-1].is==0)
            return To(x,y-1);
        if(a[x][y+1].is==0)
            return To(x,y+1);
    }
    if(a[x][y].data=='+'){
        if(a[x][y-1].data=='-'&&a[x][y-1].is==0)
            return To(x,y-1);
        if(a[x][y+1].data=='-'&&a[x][y+1].is==0)
            return To(x,y+1);
        if(a[x+1][y].data=='|')
            return To(x+1,y);
        if(a[x+1][y].data=='-')
            return a[x+1][y].which;
    }
    if(a[x][y].data=='|'){
        if(a[x+1][y].data=='+')
            return To(x+1,y);
        if(a[x+1][y].data=='|')
            return To(x+1,y);
        if(a[x+1][y].data=='-')
            return a[x+1][y].which;
    }
}
void Run(int now){   //最后的输出查找
    for(int x=b[now].xe;x>=b[now].xs;x--){
        a[x][b[now].ye].is=1;
        a[x][b[now].ys].is=1;
        if(a[x][b[now].ys-1].data=='-'||a[x][b[now].ys-1].data=='+')
            Run(To(x,b[now].ys-1));
        if(a[x][b[now].ye+1].data=='-'||a[x][b[now].ye+1].data=='+')
            Run(To(x,b[now].ye+1));
    }
    printf("%d\n",now);
    return;
}
int Num(int x,int y){//找数字
    int now=0;
    int x0=x,y0=y;
    while(a[x0][y0].data>='0'&&a[x0][y0].data<='9'){
        now=now*10+(a[x0][y0].data-'0');
        y0++;
    }
    return now;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j].data;
    for(int i=1;i<+n;i++)
        for(int j=1;j<=m;j++)
            a[i][j].which=-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(a[i][j].data>='0'&&a[i][j].data<='9'&&a[i][j].is==0)
                Search(i,j,Num(i,j));
        }
    Run(1);
    return 0;
}
  • 那大概就是如此
相关标签: NOIP