帶你飛專題1

code c++ fly

學習算法

1.poj1321

  • 類似8皇后,使用遞歸解
#include <iostream>
using namespace std;
 
const int N = 10;
 
char g[N][N];
bool cols[N];
int n=0,k=0;
int ans;
 
void dfs(int col,int num){
    if(col == n){
        if(num == k) ans ++;
        return;
    }
    for(int i=0;i<n;i++){
        if(!cols[i] && g[col][i] == '#'){
            cols[i] = true;
            dfs(col+1,num+1);
            cols[i] = false;
        }
    }
    dfs(col+1,num);
}
 
int main() {
    while (cin >> n >> k)
    {
        if(n == -1 && k == -1) break;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin >> g[i][j];
            }
        }
        ans = 0;
        dfs(0,0);
        cout << ans << '\n';
    }
}

2.poj2251

  • 3D BFS,因為有x,y,z所以用class存取比較方便,也可以用tuple
  • 每次走過都將mp設為#,避免重複走導致TLE
#include <iostream>
#include <stdio.h>
#include <queue>
 
using namespace std;
 
int l, r, c;
char mp[31][31][31]; // z x y
int vis[31][31][31];
int s_x, s_y, s_z; // start
int e_x, e_y, e_z; // end
 
int d_x[6] = {0, 0, -1, 0, 1, 0};
int d_y[6] = {0, 0, 0, 1, 0, -1};
int d_z[6] = {1, -1, 0, 0, 0, 0};
 
class Point
{
public:
    Point(int x = 0, int y = 0, int z = 0) : _x(x), _y(y), _z(z) {};
    int _x, _y, _z;
};
 
int bfs()
{
    queue<Point> q;
    q.push(Point(s_x, s_y, s_z));
    vis[s_z][s_x][s_y] = 0;
    while (q.size())
    {
        Point p = q.front();
        q.pop();
        if (p._x == e_x && p._y == e_y && p._z == e_z)
            return vis[e_z][e_x][e_y];
        for (int i = 0; i < 6; i++)
        {
            int n_x = p._x + d_x[i];
            int n_y = p._y + d_y[i];
            int n_z = p._z + d_z[i];
            if (mp[n_z][n_x][n_y] != '#' && n_x >= 0 && n_x < r && n_y >= 0 && n_y < c && n_z >= 0 && n_z < l )
            {
                q.push(Point(n_x, n_y, n_z));
                vis[n_z][n_x][n_y] = vis[p._z][p._x][p._y] + 1;
                mp[n_z][n_x][n_y] = '#';
            }
        }
    }
    return -1;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while (cin >> l >> r >> c)
    {
        if (l == 0 && r == 0 && c == 0)
            return 0;
        for (int i = 0; i < l; i++)
        {
            for (int j = 0; j < r; j++)
            {
                for (int k = 0; k < c; k++)
                {
                    cin >> mp[i][j][k];
                    if (mp[i][j][k] == 'S')
                    {
                        s_z = i;
                        s_x = j;
                        s_y = k;
                    }
                    else if (mp[i][j][k] == 'E')
                    {
                        e_z = i;
                        e_x = j;
                        e_y = k;
                    }
                }
            }
        }
        memset(vis,-1,sizeof(vis));
        int ans = bfs();
        ans == -1 ? printf("Trapped!\n") : printf("Escaped in %d minute(s).\n", ans);
    }
}

3.poj3278

  • dis[now]+1代表從現在節點移動到下一個節點的最短距離，下一個節點有可能是dis[now+1]/dis[now-1]/dis[now*2]
  • 如果說是小於的話，就跟新值
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
const int maxn = 100000;
int n,k,dis[maxn+1],now;
queue<int> q;
 
int main(){
    while(cin >> n >> k){
        memset(dis,0x3f,sizeof(dis));
        q.push(n);
        dis[n] = 0;
        while(q.size()){
            now = q.front();
            q.pop();
            if(now + 1 <= maxn && dis[now]+1 < dis[now+1]){
                q.push(now+1);
                dis[now+1] = dis[now]+1;
            }
            if(now-1 >= 0 && dis[now]+1 < dis[now-1]){
                q.push(now-1);
                dis[now-1] = dis[now]+1;
            }
            if(now*2 <= maxn && dis[now]+1 < dis[now*2]){
                q.push(now*2);
                dis[now*2] = dis[now]+1;
            }
        }
        cout << dis[k] << '\n';
    }
}

4.poj3279

  • 由於需要枚舉翻轉次數有可能會造成太大的時間消耗,因此使用狀態壓縮解決
  • 狀態枚舉
    • 1 << m 表示將2^m種可能性全部枚舉。對於每個可能的 i，它代表著第一行的翻轉情況。
for (int i = 0; i < (1 << m); i++) {
    slove(i);
}
  • 狀態處理
    • 通過 `x >> i & 1`` 來檢查 x 的第 i 位是否為 1。如果是 1，則翻轉第 0 行的第 i 列。
if ((x >> i) & 1) {
    reverse_(0, i);
}
  • 後續處理
    • 當處理完第一行的翻轉後，後續每一行的翻轉決定於上一行是否有 1。如果上一行的某個格子是 1，那麼對應的當前行的格子就必須翻轉，這樣才能將上一行的格子變成 0
if (temp[i - 1][j]) {
    reverse_(i, j);
}
#include <cstring>
#include <stdio.h>
using namespace std;
const int INF = 0x3f3f3f;
const int N = 15 + 5;
int board[N][N], temp[N][N], vis[N][N], ans[N][N];
int n, m;
int min_step_ = INF;
 
int dict[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
 
void reverse_(int u, int v) {
  vis[u][v] = 1;
  temp[u][v] ^= 1;
  for (int i = 0; i < 4; i++) {
    int x = u + dict[i][0];
    int y = v + dict[i][1];
    if (x >= 0 && x < n && y >= 0 && y < m) {
      temp[x][y] ^= 1;
    }
  }
}
 
bool check() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (temp[i][j] == 1)
        return false;
    }
  }
  return true;
}
 
void slove(int x) {
  memcpy(temp, board, sizeof(board));
  memset(vis, 0, sizeof(vis));
 
  int cnt = 0;
  for (int i = 0; i < m; i++) {
    // 狀態壓縮
    if ((x >> i) & 1) {
      cnt++;
      reverse_(0, i);
    }
  }
 
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (temp[i - 1][j] == 1) {
        cnt++;
        reverse_(i, j);
      }
    }
  }
 
  if (check() && cnt < min_step_) {
    min_step_ = cnt;
    memcpy(ans, vis, sizeof(vis));
  }
}
 
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      scanf("%d", &board[i][j]);
    }
  }
 
  // 枚舉
  for (int i = 0; i < (1 << m); i++) {
    slove(i);
  }
 
  if (min_step_ == INF) {
    printf("IMPOSSIBLE");
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m - 1; j++) {
        printf("%d ", ans[i][j]);
      }
      printf("%d\n", ans[i][m - 1]);
    }
  }
}