[算法导论] 搭积木

本文主要是介绍[算法导论] 搭积木，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<iostream>
#include<string>
#include<bits/stdc++.h>
using namespace std;
int mv_on(int n1,int n2,int dp[25][25],int n){ //mv a on b a清空放b清空之上
    int ix1=-1,ix2=-1,iy1=-1,iy2=-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<25;j++){
            if(ix1==-1 && n1==dp[i][j]){
                ix1=i;iy1=j;
            };
            if(ix2==-1 && n2==dp[i][j]){
                ix2=i;iy2=j;
            };
        }
        if(ix1!=-1 && ix2!=-1){
                break;
        };
    }
    if(ix1==ix2){return 1;}
    for(int i=1;i<25-iy1;++i){
        for(int j=0;j<25;++j){
            if(dp[ix1][iy1+i]!=-1&&dp[dp[ix1][iy1+i]][j]==-1){
                dp[dp[ix1][iy1+i]][j]=dp[ix1][iy1+i];
                dp[ix1][iy1+i]=-1;
                break;
            }
        }
    }
    for(int i=1;i<25-iy2;++i){
        for(int j=0;j<25;++j){
            if(dp[ix2][iy2+i]!=-1&&dp[dp[ix2][iy2+i]][j]==-1){
                dp[dp[ix2][iy2+i]][j]=dp[ix2][iy2+i];
                dp[ix2][iy2+i]=-1;
                break;
            }
        }
    }
    dp[ix2][iy2+1]=dp[ix1][iy1];
    dp[ix1][iy1]=-1;
    return 1;
}
int mv_ov(int n1,int n2,int dp[25][25],int n){ //mv a ov b a清空放b之上
    int ix1=-1,ix2=-1,iy1=-1,iy2=-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<25;j++){
            if(ix1==-1 && n1==dp[i][j]){
                ix1=i;iy1=j;
            };
            if(ix2==-1 && n2==dp[i][j]){
                ix2=i;iy2=j;
            };
        }
        if(ix1!=-1 && ix2!=-1){
                break;
        };
    }
    if(ix1==ix2){return 1;}
    for(int i=1;i<25-iy1;++i){
        for(int j=0;j<25;++j){
            if(dp[ix1][iy1+i]!=-1&&dp[dp[ix1][iy1+i]][j]==-1){
                dp[dp[ix1][iy1+i]][j]=dp[ix1][iy1+i];
                dp[ix1][iy1+i]=-1;
                break;
            }
        }
    }
    for(int j=1;j<25-iy2;++j){
        if(dp[ix2][iy2+j]==-1){
            dp[ix2][iy2+j]=dp[ix1][iy1];
            dp[ix1][iy1]=-1;
            break;
        }
    }
    return 1;
}
int st_on(int n1,int n2,int dp[25][25],int n){ //st a on b a放b清空之上
    int ix1=-1,ix2=-1,iy1=-1,iy2=-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<25;j++){
            if(ix1==-1 && n1==dp[i][j]){
                ix1=i;iy1=j;
            };
            if(ix2==-1 && n2==dp[i][j]){
                ix2=i;iy2=j;
            };
        }
        if(ix1!=-1 && ix2!=-1){
                break;
        };
    }
    if(ix1==ix2){return 1;}
    for(int i=1;i<25-iy2;++i){
        for(int j=0;j<25;++j){
            if(dp[ix2][iy2+i]!=-1&&dp[dp[ix2][iy2+i]][j]==-1){
                dp[dp[ix2][iy2+i]][j]=dp[ix2][iy2+i];
                dp[ix2][iy2+i]=-1;
                break;
            }
        }
    } //b上清空到原位置
    int c=0;
    for(int j=1;j<25-iy2;++j){
        if(dp[ix1][iy1+c]!=-1&&dp[ix2][iy2+j]==-1){
            dp[ix2][iy2+j]=dp[ix1][iy1+c];
            dp[ix1][iy1+c]=-1;
         }
        c++;
    }
    return 1;
}
int st_ov(int n1,int n2,int dp[25][25],int n){ //st a ov b a放b之上
    int ix1=-1,ix2=-1,iy1=-1,iy2=-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<25;j++){
            if(ix1==-1 && n1==dp[i][j]){
                ix1=i;iy1=j;
            };
            if(ix2==-1 && n2==dp[i][j]){
                ix2=i;iy2=j;
            };
        }
        if(ix1!=-1 && ix2!=-1){
                break;
        };
    }
    if(ix1==ix2){return 1;}
    int c=0;
    for(int j=1;j<25-iy2;++j){
        if(dp[ix1][iy1+c]!=-1&&dp[ix2][iy2+j]==-1){
            dp[ix2][iy2+j]=dp[ix1][iy1+c];
            dp[ix1][iy1+c]=-1;
            c++;
        }
    }
    return 1;
}
int xh_an(int n1,int n2,int dp[25][25],int n){ //xh a an b 交换列
    int ix1=-1,ix2=-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<25;j++){
            if(ix1==-1 && n1==dp[i][j]){
                ix1=i;
            };
            if(ix2==-1 && n2==dp[i][j]){
                ix2=i;
            };

        }
        if(ix1!=-1 && ix2!=-1){
                break;
        };
    }
    if(ix1==ix2){return 1;}
    int tmp[25]={-1};//初始化为-1
    for(int i=0;i<25;i++){
        tmp[i]=dp[ix1][i];
    }
    for(int i=0;i<25;i++){
        dp[ix1][i]=dp[ix2][i];
    }
    for(int i=0;i<25;i++){
        dp[ix2][i]=tmp[i];
    }
    return 1;
}

int jimu_main(){
    int n;string o1,o2;int n1,n2;
    cin>>n;
    int dp[25][25];//二维初始化不能用={-1}
    for(int i=0;i<25;i++){
        for(int j=0;j<25;j++){
            dp[i][j]=-1;}
    }
    for(int k=0;k<n;k++){
        dp[k][0]=k;
    }
    //操作
    //for(int i=0;i<n-1;i++){
    while(cin>>o1&&o1!="q"){
         cin>>n1>>o2>>n2;
        if(n1==n2){
            continue;
        }else if(o1=="mv"&&o2=="on"){
            mv_on(n1,n2,dp,n);
        }else if(o1=="mv"&&o2=="ov"){
            mv_ov(n1,n2,dp,n);
        }else if(o1=="st"&&o2=="on"){
            st_on(n1,n2,dp,n);
        }else if(o1=="st"&&o2=="ov"){
            st_ov(n1,n2,dp,n);
        }else if(o1=="xh"&&o2=="an"){
            xh_an(n1,n2,dp,n);
        }
    }
    for(int j=0;j<n;j++){
        cout<<j<<":";
        for(int x=0;dp[j][x]!=-1&&x<25;x++){
            cout<<" "<<dp[j][x];
        }
        cout<<endl;
    }
    return 1;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
void getCommand(string &line, string &command, int &a, string &opt, int &b) {
  int cnt = 0;
  string tmp = "";
  int num = 0;
  for (char x: line) {
    if(x == ' ') {
      if(cnt == 0) command = tmp;
      else if(cnt == 1) a = num;
      else if(cnt == 2) opt = tmp;
      else if(cnt == 3) b = num;
      cnt ++;
      num = 0;
      tmp = "";
    }else {
      if(cnt == 0 || cnt == 2) tmp += x;
      else if(cnt == 1 || cnt == 3) num = num * 10 + x - '0';
    }
  }
  b = num;
}
void findIJ(vector<vector<int> > &v, int n, int a, int b, int &a_i, int &a_j, int &b_i, int &b_j) {
  a_i = -1; a_j = -1; b_i = -1; b_j = -1;
  for (int i = 0; i < n; ++ i) {
    for (int j = 0; j < v[i].size(); ++ j) {
      if(v[i][j] == a) {
        a_i = i; a_j = j;
      }
      if(v[i][j] == b) {
        b_i = i; b_j = j;
      }
    }
  }
}
void mvOn(vector<vector<int> > &v, int a_i, int a_j, int b_i, int b_j) {
  if(a_i == -1 || a_j == -1 || b_i == -1 || b_j == -1) return;
  int a = v[a_i][a_j], b = v[b_i][b_j];
  if(a == b || a_i == b_i) return;
  // for (int i = v[a_i].size() - 1; i > a_j; -- i) {
  //   if(a_i == v[a_i][i]) return ;
  // }
  // for (int i = v[b_i].size() - 1; i > b_j; -- i) {
  //   if(b_i == v[b_i][i]) return;
  // }
  for (int i = v[a_i].size() - 1; i >= a_j; -- i) {
    if(i != a_j) v[v[a_i][i]].push_back(v[a_i][i]);
    v[a_i].pop_back();
  }
  for (int i = v[b_i].size() - 1; i > b_j; -- i) {
    v[v[b_i][i]].push_back(v[b_i][i]);
    v[b_i].pop_back();
  }
  v[b_i].push_back(a);
}
void mvOv(vector<vector<int> > &v, int a_i, int a_j, int b_i, int b_j) {
  if(a_i == -1 || a_j == -1 || b_i == -1 || b_j == -1) return;  
  int a = v[a_i][a_j], b = v[b_i][b_j];
  if(a == b || a_i == b_i) return;
  // for (int i = v[a_i].size() - 1; i > a_j; -- i) {
  //   if(a_i == v[a_i][i]) return ;
  // }
  for (int i = v[a_i].size() - 1; i >= a_j; -- i) {
    if(i != a_j) v[v[a_i][i]].push_back(v[a_i][i]);
    v[a_i].pop_back();
  }
  v[b_i].push_back(a);
}
void stOn(vector<vector<int> > &v, int a_i, int a_j, int b_i, int b_j) {
  if(a_i == -1 || a_j == -1 || b_i == -1 || b_j == -1) return;  
  int a = v[a_i][a_j], b = v[b_i][b_j];
  if(a == b || a_i == b_i) return;
  // for (int i = v[b_i].size() - 1; i > b_j; -- i) {
  //   if(b_i == v[b_i][i]) return ;
  // }
  for (int i = v[b_i].size() - 1; i > b_j; -- i) {
    v[v[b_i][i]].push_back(v[b_i][i]);
    v[b_i].pop_back();
  }
  for (int i = a_j; i < v[a_i].size(); ++ i) {
    v[b_i].push_back(v[a_i][i]);
  }
  for (int i = v[a_i].size() - 1; i >= a_j; -- i) {
    v[a_i].pop_back();
  }
}
void stOv(vector<vector<int> > &v, int a_i, int a_j, int b_i, int b_j) {
  if(a_i == -1 || a_j == -1 || b_i == -1 || b_j == -1) return;  
  int a = v[a_i][a_j], b = v[b_i][b_j];
  if(a == b || a_i == b_i) return;
  for (int i = a_j; i < v[a_i].size(); ++ i) {
    v[b_i].push_back(v[a_i][i]);
  }
  for (int i = v[a_i].size() -1; i >= a_j; -- i) {
    v[a_i].pop_back();
  }
}
void xhAn(vector<vector<int> > &v, int a, int b) {
  if(a == -1 || b == -1 || a == b) return;  
  swap(v[a], v[b]);
}
int main() {
  int n, a = -1, b = -1;
  int a_i, a_j, b_i, b_j;
  string line, command = "", opt = "";
  cin >> n;
  getchar();
  vector<vector<int> > v(n+5, vector<int>(0));
  for (int i = 0; i < n; ++ i) v[i].push_back(i);
  while(getline(cin, line)) {
    if(line == "q") break;
    getCommand(line, command, a, opt, b);
    if(command == "mv" && opt == "on") {
      findIJ(v, n, a, b, a_i, a_j, b_i, b_j);
      mvOn(v, a_i, a_j, b_i, b_j);
    }else if(command == "mv" && opt == "ov") {
      findIJ(v, n, a, b, a_i, a_j, b_i, b_j);
      mvOv(v, a_i, a_j, b_i, b_j);
    }else if(command == "st" && opt == "on") {
      findIJ(v, n, a, b, a_i, a_j, b_i, b_j);
      stOn(v, a_i, a_j, b_i, b_j);
    }else if(command == "st" && opt == "ov") {
      findIJ(v, n, a, b, a_i, a_j, b_i, b_j);
      stOv(v, a_i, a_j, b_i, b_j);
    }else if(command == "xh" && opt == "an") {
      findIJ(v, n, a, b, a_i, a_j, b_i, b_j);
      xhAn(v, a_i, b_i);
    }
  }
  for (int i = 0; i < n; ++ i) {
    if(v[i].size() == 0) {
      printf("%d:\n", i);
    }else {
      printf("%d:", i);
      for (int x: v[i]) {
        printf(" %d", x);
      }
      printf("\n");
    } 
  }
  return 0;
}

class buildingBlocks():
    
    def __init__(self,n) -> None:
        self.block_num = n
        self.blocks = {i:[i] for i in range(n)}
    def mv_on(self,a,b):
        pos_a,pos_b = self.search(a),self.search(b)
        if pos_a == pos_b:
            return
        self.reset(pos_a,a)
        self.reset(pos_b,b)
        self.blocks[pos_a].pop()
        self.blocks[pos_b].append(a)
    def mv_ov(self,a,b):
        pos_a,pos_b = self.search(a),self.search(b)
        if pos_a == pos_b:
            return
        self.reset(pos_a,a)
        self.blocks[pos_a].pop()
        self.blocks[pos_b].append(a)
    def st_on(self,a,b):
        pos_a,pos_b = self.search(a),self.search(b)
        if pos_a == pos_b:
            return
        self.reset(pos_b,b)
        result = self.getBlockAboutTarget(pos_a,a)[::-1]
        self.blocks[pos_b] += result
    def st_ov(self,a,b):
        pos_a,pos_b = self.search(a),self.search(b)
        if pos_a == pos_b:
            return
        result = self.getBlockAboutTarget(pos_a,a)[::-1]
        self.blocks[b] += result
    def xh_an(self,a,b):
        pos_a,pos_b = self.search(a),self.search(b)
        if pos_a == pos_b:
            return
        self.blocks[pos_a],self.blocks[pos_b] = self.blocks[pos_b],self.blocks[pos_a]
    def reset(self,pos,target):
        for i in reversed(range(len(self.blocks[pos]))):
            cur_block = self.blocks[pos].pop()
            if cur_block == target:
                self.blocks[pos].append(cur_block)
                break
            else:
                self.blocks[cur_block].insert(0,cur_block)
    def search(self,id):
        for k,v in self.blocks.items():
            if id in v:
                return k
    def getBlockAboutTarget(self,pos,target):
        result = []
        while True:
            temp = self.blocks[pos].pop()
            result.append(temp)
            if temp == target:
                break     
        return result
    def printInfo(self):
        for k,v in self.blocks.items():
            if v == []:
                print("{}:".format(k))
            else:
                print("{}: {}".format(k," ".join([str(b) for b in v])))
def building(blocks):
    try:
        while True:
            instruction = input()
            if instruction == 'q':
                break
            else:
                instruction = instruction.split()
            a,b = int(instruction[1]),int(instruction[3])
            if a == b:
                continue
            operator = instruction[0] + " " + instruction[2]
            if operator == "mv on":
                blocks.mv_on(a,b)
            elif operator == "mv ov":
                blocks.mv_ov(a,b)
            elif operator == "st on":
                blocks.st_on(a,b)
            elif operator == "st ov":
                blocks.st_ov(a,b)
            elif operator == "xh an":
                blocks.xh_an(a,b)
    except:
        pass
    
if __name__ == "__main__":
    n = int(input())
    bb = buildingBlocks(n)
    building(bb)
    bb.printInfo()

这篇关于[算法导论] 搭积木的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！