C++奥赛一本通刷题记录(回溯)

2017.11.13 By gwj1139177410

1. LETTERS openjudge156

   #include<iostream> //bugs:cin+*char[] will boom
   #include<string>
   #include<cstring>
   using namespace std;
   const int maxn = 30;
   int r, s, cnt, ans, ha[maxn*10];
   string a[maxn];
   const int dx[] = {0,1,0,-1};
   const int dy[] = {-1,0,1,0};
   void dfs(int x, int y){
      ans = max(ans, cnt);
      for(int i = 0; i < 4; i++){
          int nx = x+dx[i], ny = y+dy[i];
          if(nx<0||nx>=r||ny<0||ny>=s||ha[(int)a[nx][ny]])continue;
          ha[(int)a[nx][ny]] = 1;  cnt++;
          dfs(nx,ny);
          ha[(int)a[nx][ny]] = 0;  cnt--;
      }
   }
   int main(){
      cin>>r>>s;
      for(int i = 0; i < r; i++)cin>>a[i];
      ha[(int)a[0][0]] = 1; cnt = 1;
      dfs(0,0);
      cout<<ans<<"\n";
      return 0;
   }
   

2. 八皇后问题 openjudge1700

   //bugs:鬼畜的题目，列优先处理
   #include<iostream>
   using namespace std;
   int n = 8, c[10], ma[10][10], cnt; //c[]记录每一列的皇后所在的行的位置, ma[][]是整个矩阵
   void dfs(int cur){
      if(cur == 8){
          cout<<"No. "<<++cnt<<"\n";
          for(int i = 0; i < 8; i++){
              for(int j = 0; j < 8; j++)
                  cout<<ma[i][j]<<" ";
              cout<<"\n";
          }
      }else for(int i = 0; i < 8; i++){//尝试每一行是否能填
          int ok = 1;
          for(int j = 0; j < cur; j++)
              if(c[j]==i||cur-i==j-c[j]||cur+i==j+c[j])
                  { ok = 0; break; }
          if(ok){
              c[cur] = i;
              ma[i][cur] = 1;
              dfs(cur+1);
              ma[i][cur] = 0;
          }
      }
   }
   int main(){
      dfs(0);
      return 0;
   }
   

3. 八皇后 openjudge1756

   //枚举加打表
   #include<iostream>
   #include<vector>
   using namespace std;
   vector<int>ans;
   int n = 8, c[10];
   void dfs(int cur){
      if(cur == n){
          int res = 0;
          for(int i = 0; i < 8; i++)res = res*10+c[i];
          ans.push_back(res);
      }else for(int i = 1; i <= 8; i++){
          int ok = 1;
          for(int j = 0; j < cur; j++)
              if(c[j]==i||c[j]+j==i+cur||c[j]-j==i-cur)
                  {ok = 0; break;}
          if(ok){
              c[cur] = i;
              dfs(cur+1);
          }
      }
   }
   int main(){
      dfs(0);
      int T;  cin>>T;
      while(T--){
          int x;  cin>>x;
          cout<<ans[x-1]<<"\n";
      }
      return 0;
   }
   

4. 迷宫 openjudge1792

   //模板
   #include<iostream>
   #include<string>
   #include<cstring>
   using namespace std;
   const int maxn = 1010;
   int n, x1, y1, x2, y2, vis[maxn][maxn], flag;
   string a[maxn];
   const int dx[] = {1,0,-1,0};
   const int dy[] = {0,1,0,-1};
   void dfs(int x, int y){
      if(x<0||x>=n||y<0||y>=n||a[x][y]=='#'||vis[x][y])return ;
      vis[x][y] = 1;
      if(x==x2&&y==y2)flag = 1;
      else for(int i = 0; i < 4; i++){
          dfs(x+dx[i],y+dy[i]);
      }
   }
   int main(){
      int T;  cin>>T;
      while(T--){
          cin>>n;
          for(int i = 0; i < n; i++)cin>>a[i];
          cin>>x1>>y1>>x2>>y2;
          flag = 0;
          if(a[x1][y1]!='#'&&a[x2][y2]!='#'){
              memset(vis,0,sizeof(vis));
              dfs(x1,y1);
          }
          if(flag)cout<<"YES\n";else cout<<"NO\n";
      }
      return 0;
   }
   

5. 红与黑 openjudge1818

   //模板
   #include<iostream>
   #include<string>
   #include<cstring>
   using namespace std;
   const int maxn = 50;
   int n, m, x1, y1, vis[maxn][maxn], ans;
   string a[maxn];
   const int dx[] = {1,0,-1,0};
   const int dy[] = {0,1,0,-1};
   void dfs(int x, int y){
      ans++;  vis[x][y] = 1;
      for(int i = 0; i < 4; i++){
          int nx = x+dx[i], ny = y+dy[i];
          if(nx<0||nx>=n||ny<0||ny>=m)continue;
          if(vis[nx][ny]||a[nx][ny]=='#')continue;
          dfs(nx,ny);
      }
   }
   int main(){
      while(cin>>m>>n &&m &&n){
          for(int i = 0; i < n; i++){
              cin>>a[i];
              for(int j = 0; j < m; j++)
                  if(a[i][j]=='@'){x1=i;y1=j;}
          }
          memset(vis,0,sizeof(vis));  ans = 0;
          dfs(x1,y1);
          cout<<ans<<"\n";
      }
      return 0;
   }
   

6. 棋盘问题 openjudge323

   #include<iostream>
   #include<string>
   #include<cstring>
   using namespace std;
   const int maxn = 20;
   int n, k, vis[maxn], ans; //vis[i]:第i行是否可填
   string a[maxn];
   void dfs(int cur, int sum){
      if(sum > k)ans++;
      else for(int i = cur; i < n; i++){//枚举从哪一行开始填
          for(int j = 0; j < n; j++){//枚举填在第几列
              if(a[i][j]=='#'&&!vis[j]){
                  vis[j] = 1;
                  dfs(i+1, sum+1);
                  vis[j] = 0;
              }
          }
      }
   }
   int main(){
      ios::sync_with_stdio(false);
      while(cin>>n>>k &&n!=-1&&k!=-1){
          for(int i = 0; i < n; i++)cin>>a[i];
          memset(vis,0,sizeof(vis)); ans = 0;  dfs(0,1);
          cout<<ans<<"\n";
      }
      return 0;
   }
   

7. 取石子游戏 openjudge6266

   //博弈论。。。
   #include<iostream>
   #include<algorithm>
   using namespace std;
   bool xht(int a, int b){
      if(a%b==0)return true;
      if((int)(a/b)>=2)return true;//bugs注意取整
      if((int)(a/b)==1)return !xht(b,a-b);
   }
   int main(){
      int a, b;
      while(cin>>a>>b &&a&&b){
          if(a<b)swap(a,b);
          if(xht(a,b))cout<<"win\n";
          else cout<<"lose\n";
      }
      return 0;
   }
   

8. 马走日 openjudge8465

   //bugs:马走日，马走的是日，马走的是日字型。。。。
   #include<iostream>
   #include<cstring>
   using namespace std;
   const int maxn = 20;
   int n, m, x, y, vis[maxn][maxn], cnt, ans;
   const int dx[] = {1,-1,1,-1,2,-2,2,-2};
   const int dy[] = {2,2,-2,-2,1,1,-1,-1};
   void dfs(int x, int y){
      if(x<0||x>=n||y<0||y>=m||vis[x][y])return ;
      vis[x][y] = 1;
      if(cnt == n*m-1)ans++;
      for(int i = 0; i < 8; i++){
          cnt++;
          dfs(x+dx[i],y+dy[i]);
          cnt--;
      }
      vis[x][y] = 0;
   }
   int main(){
      int T;  cin>>T;
      while(T--){
          cin>>n>>m>>x>>y;
          memset(vis,0,sizeof(vis));
          cnt = ans = 0;
          dfs(x,y);
          cout<<ans<<"\n";
      }
      return 0;
   }
   

9. 单词接龙 openjudge8783

   //直接搜索就好啦，几乎没什么技巧，就是状态建模会有点难想到(应该有多种)
   //包含的情况可以证明是不需要考虑的,因为包含后一定不会比不包含要来的长
   #include<iostream>
   #include<algorithm>
   #include<string>
   using namespace std;
   const int maxn = 30;
   int n, ans, used[maxn];
   string w[maxn];
   //找到a的末尾与b的前端重复的子串并返回其长度
   int find(string a, string b){
      int mm = min(a.size(), b.size());
      for(int i = 1; i <= mm; i++)
          if(a.substr(a.size()-i)==b.substr(0,i))
              return i;
      return 0;
   }
   //深度优先搜索寻找解, 状态：cur为当前字符串
   void dfs(string cur){
      ans = max(ans, (int)cur.size());
      for(int i = 1; i <= n; i++)if(used[i]<2){
          int t = find(cur, w[i]);
          if(t == cur.size() && cur!=w[0])continue;//包含关系
          if(t){
              used[i]++;
              dfs(cur.substr(0,cur.size()-t)+w[i]);
              used[i]--;
          }
      }
   }
   int main(){
      cin>>n;
      for(int i = 1; i <= n; i++)cin>>w[i];
      cin>>w[0];
      dfs(w[0]);
      cout<<ans<<"\n";
      return 0;
   }
   

10. 分成互质组 openjudge7834
    cpp
//数据太水怪我咯？。。思路是每次对于新的一个数，与各组比对是否互质，若没有组能加就添加新组。
#include<iostream>
using namespace std;
const int maxn = 20;
int n, a[maxn], vis[maxn], cmp[maxn], cnt;
int gcd(int a, int b){
return !b?a:gcd(b,a%b);
}
int main(){
cin>>n;
for(int i = 0; i < n; i++)cin>>a[i];
//1. 每次找出未分类的值并将其放入新的类别
for(int i = 0; i < n; i++)if(!vis[i]){
vis[i] = 1; cmp[i]=++cnt;
//2. 找出所有未分类的值中与当前值所在类别全部互质的值并加入该类
for(int j = 0; j < n; j++)if(!vis[j]){
int ok = 1;
for(int k = 0; k < n; k++)if(cmp[k]==cmp[i]){//遍历当前值所在类别的值
if(gcd(a[j],a[k])!=1)ok = 0;
}
if(ok){
vis[j] = 1;
cmp[j] = cnt;
}
}
}
cout<<cnt<<"\n";
return 0;
}

cpp
//f[i][j],选到了第i个数，现在有j个集合
//注:当要把这个数放进来之前前面的数在放进来的时候都已经判断好了
#include<iostream>
using namespace std;
int n, a[20], b[20], ans;
int gcd(int a, int b){
return !b?a:gcd(b,a%b);
}
void dfs(int x, int y){
int flag = 1;
if(x==n){ ans = min(ans,y); return ;}
else for(int i = 1; i <= y; i++){//1.遍历每一个已有类别
int ok = 1;
for(int j = 0; j < n; j++)if(b[j]==i)//2.遍历该类别所有数
if(gcd(a[j],a[x])!=1){ ok=0; break; }
if(ok){//3.如果满足全部互质,就加入该类,并判断下一个数
flag = 0; //如果存在不互质,就不用新建组
b[x] = i;
dfs(x+1,y);
b[x] = 0;
}
}
if(flag){//4.如果没有与当前数互质的类别,就新建一个类别
b[x] = y+1;
dfs(x+1,y+1);
b[x] = 0;
}
}
int main(){
cin>>n;
for(int i = 0; i < n; i++)cin>>a[i];
b[0]=1; ans=0xffffff;
dfs(1,1);
cout<<ans<<"\n";
return 0;
}


11. 放苹果 openjudge666

    //这都第几遍了啊
    #include<iostream>
    using namespace std;
    int f(int n, int m){
        if(n==0||m==1)return 1;
        if(n>=m)return f(n-m,m)+f(n,m-1);
        else return f(n,m-1);
    }
    int main(){
        int T;  cin>>T;
        while(T--){
            int n, m;  cin>>n>>m;
            cout<<f(n,m)<<"\n";
        }
        return 0;
    }
    

    ​