蒟蒻的写题方法的探索

1.先写大体框架，再写小函数与变量

测试题目：https://www.acwing.com/problem/content/174/

框架如下:

#include<bits/stdc++.h>
using namespace std;

struct rec{
    int x,y,lie;
}st,ed;

void get_st_ed()
{
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    {
        
    }
}

void input()
{
    for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
    get_st_ed();
}

int work()
{
    queue<rec>q;
    q.push(st);
    while(!q.empty())
    {
        rec now=q.front(); q.pop();
        for(int i=0;i<4;++i)
        {
            rec nxt;
            nxt.x=now.x+nxtx[now.lie][i];
            nxt.y=now.y+nxty[now.lie][i];
            nxt.lie=nxtlie[now.lie][i];
            if(!valid(nxt)) continue;
            if(d[nxt.x][nxt.y][nxt.lie]==-1)
            {
                d[nxt.x][nxt.y][nxt.lie]=d[now.x][now.y][now.lie]+1;
                if(nxt.x==ed.x&&nxt.y==ed.y&&nxt.lie==ed.lie)
                    return d[nxt.x][nxt.y][nxt.lie];
            }
        }
    }
    return -1;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF && n && m)
    {
        input();
        int ans=work();
        if(ans==-1) cout<<"Impossible";
        else cout<<ans;
        cout<<'\n';
    }
    return 0;
}

完整代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
const int li=3;

struct rec{
    int x,y,lie;
}st,ed;

int n,m;
int d[maxn][maxn][li];
char s[maxn][maxn];

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

bool valid(int x,int y)
{
    return (x>=1&&y>=1&&x<=n&&y<=m);
}

void get_st_ed()
{
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    if(s[i][j]=='O') {
        ed.x=i, ed.y=j, ed.lie=0;
        s[i][j]='.';
    }
    else if(s[i][j]=='X') {
        for(int k=0;k<4;++k)
        {
            int nx=i+dx[k], ny=j+dy[k];
            if(!valid(nx,ny) || s[nx][ny]!='X') continue;
            st.x=min(i,nx), st.y=min(j,ny);
            if(k==0||k==1) st.lie=1;
            if(k==2||k==3) st.lie=2;
            s[i][j]=s[nx][ny]='.';
        }
        if(s[i][j]=='X') {
            s[i][j]='.';
            st.x=i, st.y=j;
            st.lie=0;
        }
    }
}

void input()
{
    for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
    get_st_ed();
}

int nxtx[li][4]={{-2,1,0,0},{-1,2,0,0},{-1,1,0,0}};
int nxty[li][4]={{0,0,-2,1},{0,0,-1,1},{0,0,-1,2}};
int nxtlie[li][4]={{1,1,2,2},{0,0,1,1},{2,2,0,0}};

bool valid(rec &tmp)
{
    if(!valid(tmp.x,tmp.y)) return false;
    if(s[tmp.x][tmp.y]=='#') return false;
    if(tmp.lie==0 && s[tmp.x][tmp.y]=='E') return false;
    if(tmp.lie==1 && (s[tmp.x+1][tmp.y]=='#' || !valid(tmp.x+1,tmp.y))) return false;
    if(tmp.lie==2 && (s[tmp.x][tmp.y+1]=='#' || !valid(tmp.x,tmp.y+1))) return false;
    return true;
}

int work()
{
    memset(d,-1,sizeof d);
    queue<rec>q;
    q.push(st); d[st.x][st.y][st.lie]=0;
    while(!q.empty())
    {
        rec now=q.front(); q.pop();
        for(int i=0;i<4;++i)
        {
            rec nxt;
            nxt.x=now.x+nxtx[now.lie][i];
            nxt.y=now.y+nxty[now.lie][i];
            nxt.lie=nxtlie[now.lie][i];
            if(!valid(nxt)) continue;
            if(d[nxt.x][nxt.y][nxt.lie]==-1)
            {
                d[nxt.x][nxt.y][nxt.lie]=d[now.x][now.y][now.lie]+1;
                q.push(nxt);
                if(nxt.x==ed.x&&nxt.y==ed.y&&nxt.lie==ed.lie)
                    return d[nxt.x][nxt.y][nxt.lie];
            }
        }
    }
    return -1;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF && n && m)
    {
        input();
//      printf("%d %d %d\n",st.x,st.y,st.lie);
//      printf("%d %d %d\n",ed.x,ed.y,ed.lie);
        // accepted in test of get_st_ed();
        int ans=work();
        if(ans==-1) cout<<"Impossible";
        else cout<<ans;
        cout<<'\n';
    }
    return 0;
}

总结：个人应用这种方法时，写代码时间主要用在DEBUG上，框架不易出错，小函数容易出错，是我的锅qwq

蒟蒻的写题方法的探索

原文：https://www.cnblogs.com/tztqwq/p/12000815.html