头像

大树101




离线:1天前


最近来访(102)
用户头像
Loki
用户头像
冬眠三个月灿烂
用户头像
爱吃干煸鱼的大布丁
用户头像
Ding-yu
用户头像
刷刷刷算法
用户头像
偶尔也会翻身的咸鱼
用户头像
梦里啥都有地竺枭
用户头像
Snow_raw
用户头像
YUMAJ
用户头像
我不是子龙
用户头像
Rain丶bow
用户头像
爱吃牛古力吗
用户头像
_lcy_
用户头像
TaoZex
用户头像
minc
用户头像
V1
用户头像
梦是回忆
用户头像
zzr0126
用户头像
_魂淡_
用户头像
我是憨憨一号

活动打卡代码 AcWing 165. 小猫爬山

大树101
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int a[N],sum[N];
int ans=N;
int n,W;
bool cmp(int a,int b)
{
    return a>b;
}

void dfs(int u,int cnt)
{
    if(cnt>ans) return ;
    if(u==n+1)
    {
        ans=cnt;
        return ;
    }
    for(int i=1;i<=cnt;i++)
    {
        if(sum[i]+a[u]<=W)
        {
            sum[i]+=a[u];
            dfs(u+1,cnt);
            sum[i]-=a[u];
        }
    }
    sum[cnt+1]=a[u];
    dfs(u+1,cnt+1);
    sum[cnt+1]-=a[u];
}

int main()
{

    cin>>n>>W;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n,cmp);
    dfs(1,0);
   cout<<ans<<endl; 
    return 0;
}


活动打卡代码 AcWing 1117. 单词接龙

大树101
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
int n;
const int N = 25;
string s[25];
int ans=0;
int st[N];
int g[N][N];
void dfs(string a,int last)//当前接龙长度 和上一个单词的编号
{
    ans=max(ans,(int)a.size());
    st[last]++;
    for(int i=1;i<=n;i++)
    {
        if(g[last][i]&&st[i]<2) dfs(a+s[i].substr(g[last][i]),i);
    }
    st[last]--;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i];
    char be;
    cin>>be;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            string a=s[i],b=s[j];
            for(int k=1;k<min((int)a.size(),(int)b.size());k++)
            {
                if(a.substr(a.size()-k,k)==b.substr(0,k))
                    {
                        g[i][j]=k;
                        break;//重合长度从小到大遍历 重合数越小 接龙长度才会越大 剪枝
                    }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(s[i][0]==be) dfs(s[i],i);
    }
    cout<<ans<<endl;
    return  0;
}


活动打卡代码 AcWing 1116. 马走日

大树101
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int n,m;
int ans=0;
int st[20][20];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void dfs(int x,int y,int cnt)
{
    if(cnt==n*m)
    {
        ans++;
        return ;
    }

    for(int i=0;i<8;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<n&&b>=0&&b<m&&!st[a][b])
        {
            st[a][b]=1;
            dfs(a,b,cnt+1);
            st[a][b]=0;
        }
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        ans=0;
        memset(st, 0, sizeof st);
        int x,y;
        cin>>n>>m>>x>>y;
        st[x][y]=1;
        dfs(x,y,1);
        cout<<ans<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

大树101
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30;
char g[N][N];
int st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    int n,m;
int dfs(int x,int y)
{
    int cnt=1;
    st[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int a=dx[i]+x,b=dy[i]+y;
        if(a>=1&&a<=n&&b>=1&&b<=m&&!st[a][b]&&g[a][b]=='.')
        {
            cnt+=dfs(a,b);
        }
    }
    return cnt;
}

int main()
{

    while(cin>>m>>n,m||n)
    {
        memset(st, 0, sizeof st);
        int x,y;
        for(int i=1;i<=n;i++) 
         for(int j=1;j<=m;j++)
         {
             cin>>g[i][j];
             if(g[i][j]=='@')
             x=i,y=j;
         }
        int t=dfs(x,y);
        cout<<t<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1112. 迷宫

大树101
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int ax,ay,bx,by;
int n;
int st[N][N];
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs(int x,int y)
{
    if(g[x][y]=='#') return 0;
    if(x==bx&&y==by) return 1;
    st[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<n&&b>=0&&b<n&&!st[a][b]&&g[a][b]=='.')
        {
          if(dfs(a,b)) return 1;
        }
    }
    return 0;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
         memset(st, 0, sizeof st);
        cin>>n;
        for(int i=0;i<n;i++) scanf("%s",g[i]);
        cin>>ax>>ay>>bx>>by;
        if(g[ax][ay]=='#'||g[bx][by]=='#')  puts("NO");
         else if(dfs(ax,ay)) puts("YES");
         else puts("NO");
    }
    return 0;
}


活动打卡代码 AcWing 190. 字串变换

大树101
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

const int N = 10;

string a[N],b[N];

int n;

int work(queue<string> &qa,unordered_map<string,int> &da,unordered_map<string,int> &db,string a[],string b[])
{
    int d=da[qa.front()];
    while (qa.size() && da[qa.front()] == d)//将到起点距离一样的点都遍历一遍
    {//遍历一层
        string t=qa.front();
        qa.pop();
       for(int i=0;i<t.size();i++)
          for(int j=0;j<n;j++)
        {
         if(t.substr(i,a[j].size())==a[j])
         {
             string state=t.substr(0,i)+b[j]+t.substr(i+a[j].size());
             if(db.count(state)) return da[t]+1+db[state];
             if(da.count(state))  continue;
             qa.push(state);
             da[state]=da[t]+1;
          }
        }
    }

     return 11;
}


int bfs(string A,string B)
{
    if(A==B) return 0;
    unordered_map<string,int> da,db;
    queue<string> qa,qb;
    qa.push(A);
    qb.push(B);
     da[A] = db[B] = 0;
     int temp=0;
    while(qa.size()&&qb.size())
    {
        temp++;
        int t;//比较起点和终点的枝条 因为如果两者是联通的情况下 我们每次从
        //伸出去的枝条数少的方向遍历 也能求得答案   剪枝
        if(qa.size()<=qb.size()) t=work(qa,da,db,a,b);
        else t=work(qb,db,da,b,a);
        if(t<=10) return t;
        if(temp>10) return 11;
    }
    return 11;
}
int main()
{
    string A,B;
    cin>>A>>B;
    while(cin>>a[n]>>b[n]) n++;

  int t=bfs(A,B);
   if(t>10) puts("NO ANSWER!");
   else cout<<t<<endl;
    return 0;
}


活动打卡代码 AcWing 175. 电路维修

大树101
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include<deque>
#define x first
#define y second

using namespace std;

const int N = 510;

typedef pair<int, int> PII;

int n,m;
char g[N][N];
int st[N][N];
int d[N][N];                          //具体看题解的图
int dx[]={-1,-1,1,1},dy[]={-1,1,-1,1};//表示单元格的四个角 也是我们遍历的点
int ix[]={-1,-1,0,0},iy[]={-1,0,-1,0};//表示基于点时单元格内的字符 四个方向的变化情况
char cs[]="\\//\\";// \表示转义字符需要两个
int bfs()
{
    memset(st, 0, sizeof st);
    memset(d, 0x3f3f, sizeof d);
    deque<PII> q;
    q.push_back({0,0});
    d[0][0]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop_front();
        int x=t.x,y=t.y;
         if(x==n&&y==m) return d[x][y];//只能才出队时判断 因为此时对于x y才是最短路
                              //因为我们队列维护的就是第一个到达(出队)的一定是最优解
        if(st[x][y]) continue;
        st[x][y]=1;//类似Dijkstra的思想 用现在已经确定的路径长度去更新后面的点
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a<0||a>n||b<0||b>m) continue;
            int ga=x+ix[i],gb=y+iy[i];
            int w=(g[ga][gb]!=cs[i]);
            int dist=d[x][y]+w;
            if(dist<d[a][b]) //类似Dijkstra的思想
            {
                 d[a][b]=dist;// 可以看作队列需要维护第一次出队的是最优解 
                        //排在前面的优先级高 先出队保证最优解 类似bfs的思想第一次遍历到的点就是最近的
                 if(!w) q.push_front({a,b});//双端队列 如果权重为0 加到队头
                 else q.push_back({a,b});// 权重为1 加到队尾
            }
        }
    }
    return 0;
}
void solve()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) scanf("%s",g[i]);

    if((n+m)&1) 
    {
        puts("NO SOLUTION");
        return ;
    }

       cout<<bfs()<<endl;
}

int main()
{
    int T;
    cin>>T;
    while(T--) solve();

    return 0;
}


活动打卡代码 AcWing 1107. 魔板

大树101
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
#define x first
#define y second

using namespace std;

unordered_map<string,int> d;//记录字符串为s的步数
unordered_map<string,pair<char,string>> pre;//记录变为字符串s的操作和之前的字符串
queue<string> q;

string move0(string s)
{
     string res="0";
     for(int i=8;i>=5;i--) res+=s[i];
     for(int i=4;i>=1;i--) res+=s[i];
     return res;
}

string move1(string s)
{
    string res="0";
    res+=s[4];
    for(int i=1;i<=3;i++) res+=s[i];
    res+=s[6];
    for(int i=7;i<=8;i++) res+=s[i];
    res+=s[5];
    return res;
}
string move2(string s)
{
    string res="0";
    res+=s[1],res+=s[7],res+=s[2],res+=s[4];
    res+=s[5],res+=s[3],res+=s[6],res+=s[8];
    return res;
}


void bfs(string be,string end)
{
    string op[3];

    q.push(be);
    while(!q.empty())
    {
        string t=q.front();
        q.pop();
        op[0]=move0(t);
        op[1]=move1(t);
        op[2]=move2(t);
        for(int i=0;i<3;i++)
        {
            string a=op[i];
            if(d.count(a)) continue;
            d[a]=d[t]+1;
            pre[a]={char(i+'A'),t};
            if(a==end) break;
            q.push(a);
        }
    }
}

int main()
{
    string be="",end="";
    be="012345678";
    end+='0';
    for(int i=1;i<=2;i++)
      for(int j=1;j<=4;j++)
        {
           int x;
           cin>>x;
            end+=char(x+'0');//int转char
        }
        bfs(be,end);
        cout<<d[end]<<endl;
        if(d[end])
        {
            string res;
         while(be!=end)
        {
            res+=pre[end].x;
            end=pre[end].y;
        }
        reverse(res.begin(),res.end());
        cout<<res<<endl;
        }

    return 0;
}



大树101
1个月前

题目链接 ACWing

为什么d.count(end)=1,但 d[end]为0 在执行bfs之后

错误的代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
#define x first
#define y second

using namespace std;

unordered_map<string,int> d;
unordered_map<string,pair<char,string>> pre;
queue<string> q;

string move0(string s)
{
     string res="0";
     for(int i=8;i>=5;i--) res+=s[i];
     for(int i=4;i>=1;i--) res+=s[i];
     return res;
}

string move1(string s)
{
    string res="0";
    res+=s[4];
    for(int i=1;i<=3;i++) res+=s[i];
    res+=s[6];
    for(int i=7;i<=8;i++) res+=s[i];
    res+=s[5];
    return res;
}
string move2(string s)
{
    string res="0";
    res+=s[1],res+=s[7],res+=s[2],res+=s[4];
    res+=s[5],res+=s[3],res+=s[6],res+=s[8];
    return res;
}


void bfs(string be,string end)
{
    string op[3];

    q.push(be);
    while(!q.empty())
    {
        string t=q.front();
        q.pop();
        op[0]=move0(t);
        op[1]=move1(t);
        op[2]=move2(t);
        for(int i=0;i<3;i++)
        {
            string a=op[i];
            if(d.count(a)) continue;
            d[a]=d[t]+1;
            pre[a]={char(i+'A'),t};
            if(a==end) break;
            q.push(a);
        }
    }
}

int main()
{
    string be="",end="";
    be="012345678";
    end+='0';
    for(int i=1;i<=2;i++)
      for(int j=1;j<=4;j++)
        {
           int x;
           cin>>x;
            end+=char(x+'0');
        }
        bfs(be,end);
        cout<<d[end]<<endl;
          cout<<d.count(end)<<endl;
        if(d[end])
        {
            string res;
         while(be!=end)
        {
            res+=pre[end].x;
            end=pre[end].y;
        }
        reverse(res.begin(),res.end());
        cout<<res<<endl;
        }

    return 0;
}


活动打卡代码 AcWing 1100. 抓住那头牛

大树101
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second

using namespace std;

const int N = 100010;

typedef pair<int, int> PII;

int st[N*2];
int q[N*2];
int d[N*2];
int n,m;
void bfs()
{
    int tt=0,hh=0;
    q[tt++]=n;
    st[n]=1;
    while(hh<tt)
    {
        int t=q[hh++];
       for(int i=0;i<3;i++)
       {
           int a;
           bool flag=false;
           if(i==0)  
           {
               a=t-1;//先减少之后再乘也是有可能的 所以不做剪枝
           }
           else if(i==1)  
           {
               a=t+1;
               if(t>m) flag=true;//如果大于m再加一 只会越来越远
           }
           else if(i==2)  
           {
               a=t*2;
                if(t>m) flag=true;//如果大于m再*2 只会越来越远
           }
           if(st[a]) continue;
           if(flag)  continue;
           q[tt++]=a;
           d[a]=d[t]+1;
           st[a]=1;
           if(a==m)
           {
               cout<<d[a]<<endl;
               return ;
           }
       }
    }
}
int main()
{
   cin>>n>>m;
   if(n>=m) cout<<n-m<<endl;
   else bfs();
    return 0;
}