pA : BishopMove
題目大意：
給定A點跟B點的座標 
，每次有四總移動方式
，請問A點到B點的最短路，若無法到達輸出-1。
，每次有四總移動方式，請問A點到B點的最短路，若無法到達輸出-1。
方法：
觀察後發現最多只需要兩步，然後就分類討論。
程式碼：
#include<bits/stdc++.h>
using namespace std;
class BishopMove{
public:
int howManyMoves(int r1, int c1, int r2, int c2){
if(abs(r2-r1)%2!=abs(c2-c1)%2) return-1;
if(r1==r2 && c1==c2) return 0;
if(abs(r2-r1)==abs(c2-c1)) return 1;
return 2;
}
};
pB : BracketExpressions
題目大意：
給你一串包含'(', ')', '[',
']', '{', '}' or 'X'的字串，X代表不確定哪種括弧，請問有幾種合法的組合。
方法：
X數量<=5，6^5爆搜。
程式碼：
#include<bits/stdc++.h>
using namespace std;
int n,flag=0;
string s;
vector<char> tmp;
char ch[6]={'(', ')', '[', ']', '{', '}'};
int check(){
stack<char> sta;
for(int i=0;i<tmp.size();i++){
if(tmp[i]==')'){
if(sta.size()==0 || sta.top()!='(') return 0;
sta.pop();
}
else if(tmp[i]==']'){
if(sta.size()==0 || sta.top()!='[') return 0;
sta.pop();
}
else if(tmp[i]=='}'){
if(sta.size()==0 || sta.top()!='{') return 0;
sta.pop();
}
else sta.push(tmp[i]);
}
if(sta.size()) return 0;
return 1;
}
void dfs(int k){
if(k==n){
if(check()) flag=1;
return;
}
if(s[k]=='X'){
for(int i=0;i<6;i++){
tmp.push_back(ch[i]);
dfs(k+1);
tmp.pop_back();
}
}
else{
tmp.push_back(s[k]);
dfs(k+1);
tmp.pop_back();
}
}
class BracketExpressions{
public:
string ifPossible(string in){
n=in.size();
s=in;
dfs(0);
if(flag) return "possible";
return "impossible";
}
};
pC : InvariantSets
題目大意：
給你一個陣列F，令一個集合S，S中若包含x則S亦包含F[x]，請問S有幾種組合。
方法：
對於每組F[x]與x建上一條邊，先做SCC把圖變成DAG，然後從根下去遍歷，對於每個點的組合數
。
。
程式碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define N 55
vector<int> s[N],g[N];
int is[N],n,pre[N],sccno[N],scc_cnt=0,dfs_cnt=0,ma[N][N],in[N];
stack<int> sta;
int dfs(int u){
int lowu,lowv,i;
sta.push(u);
lowu=pre[u]=++dfs_cnt;
for(i=0;i<s[u].size();i++){
int v=s[u][i];
if(pre[v]==0){
lowv=dfs(v);
lowu=min(lowu,lowv);
}
else if(pre[v]<pre[u] && sccno[v]==0){
lowu=min(lowu,pre[v]);
}
}
if(lowu==pre[u]){
scc_cnt++;
while(sta.size()){
int x=sta.top();
sccno[x]=scc_cnt;
sta.pop();
if(x==u) break;
}
}
return lowu;
}
ll cal(int u){
int i;
ll ans=1,tmp;
for(i=0;i<g[u].size();i++){
int v=g[u][i];
tmp=cal(v);
ans*=tmp+1;
}
return ans;
}
class InvariantSets{
public:
ll countSets(vector<int> f){
int i,j,n=f.size(),x,y;
ll ans=1,tmp;
for(i=0;i<n;i++){
s[f[i]].push_back(i);
}
for(i=0;i<n;i++){
if(pre[i]==0){
dfs_cnt=0;
dfs(i);
}
}
for(i=0;i<n;i++){
x=sccno[f[i]],y=sccno[i];
if(x==y || ma[x][y]) continue;
ma[x][y]=1;
g[x].push_back(y);
in[y]++;
}
for(i=1;i<=scc_cnt;i++){
if(in[i]==0){
tmp=cal(i);
ans*=tmp+1;
}
}
return ans;
}
};
