A.Hdu1728.逃离迷宫

思路

bfs + go straight

写法1：

#include <iostream>
#include <cstring>
#include <queue> 

using namespace std;

int t;
int n, m;
char g[110][110];
int k, sx, sy, ex, ey;
bool v[110][110];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct node
{
    int x, y;
    int k;
};

queue <node> q; 

void init()
{
    memset(v, 0, sizeof v); 
    while(q.size()) q.pop();
}

bool bfs()
{
    node now, nxt, tmp;
    now.x = sx;
    now.y = sy;
    now.k = -1;
    v[sx][sy] = 1;
    q.push(now);
    while(q.size())
    {
        now = q.front();
        q.pop();
        if(now.x == ex && now.y == ey && now.k <= k)
            return true;
        for(int i = 0; i < 4; i ++ )
        {
            nxt.x = now.x + dx[i], nxt.y = now.y + dy[i];
            while(nxt.x >= 1 && nxt.x <= n && nxt.y >= 1 && nxt.y <= m && g[nxt.x][nxt.y] == '.')
            {
                if(!v[nxt.x][nxt.y])
                {
                    nxt.k = now.k + 1;
                    v[nxt.x][nxt.y] = 1;
                    q.push(nxt);
                }
                tmp.x = nxt.x + dx[i], tmp.y = nxt.y + dy[i];
                nxt = tmp;
            }
        }
    }
    return false;
}

int main()
{
    cin >> t;
    while(t -- )
    {
        init();
        cin >> n >> m;
        for(int i = 1; i <= n; i ++ ) cin >> g[i] + 1;
        scanf("%d %d %d %d %d", &k, &sy, &sx, &ey, &ex);
        if(bfs())
            cout << "yes" << endl;
        else
            cout << "no" << endl; 
    }
    return 0;
} 

B.Hdu1584.蜘蛛牌

思路

dfs or dp

写法1：dfs

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

const int INF = 0x3f3f3f3f;

int t;
int a[11];
int ans;
int v[11];

void init()
{
    ans = INF;
    memset(v, 0, sizeof(v));
} 

void dfs(int num, int sum)
{
    if(sum >= ans) return ;
    if(num == 9)
    {
        ans = sum;
        return ;
    }
    for(int i = 1; i < 10; i ++ )
    {
        if(!v[i])
        {
            v[i] = 1;
            for(int j = i + 1; j <= 10; j ++ )
            {
                if(!v[j])
                {
                    dfs(num + 1, sum + abs(a[i] - a[j]));
                    break;
                }
            }
            v[i] = 0;
        }
    }
}

int main()
{
    cin >> t;
    while(t -- )
    {
        init();
        for(int i = 1; i <= 10; i ++ )
        {
            int x;
            cin >> x;
            a[x] = i;   
        }   
        dfs(0, 0);
        cout << ans << endl;
    } 
    return 0;
}

C.Hdu1269.迷宫城堡

思路

Tarjan + stack (+ vector)

写法1：

#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 100010;

int n, m;
int u, v, w;
int ans;
int head[N], tot;
int dfn[N], low[N], cnt;
bool vis[N];

struct Edge
{
    int v, nxt;
}edge[N << 1];

stack <int> st;

void init()
{
    tot = 1;
    cnt = ans = 0;
    for(int i = 1; i <= n; i ++ )
        head[i] = dfn[i] = low[i] = vis[i] = 0;
    while(st.size()) st.pop();
}

void add(int u, int v)
{
    edge[ ++ tot].v = v;
    edge[tot].nxt = head[u];
    head[u] = tot;
}

void Tarjan(int x)
{
    dfn[x] = low[x] = ++ cnt;
    st.push(x);
    vis[x] = 1;
    for(int i = head[x]; i; i = edge[i].nxt)
    {
        int v = edge[i].v;
        if(!dfn[v])
        {
            Tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if(vis[v])
            low[x] = min(low[x], dfn[v]);
    } 

    if(low[x] == dfn[x])
    {
        ans ++ ;
        while(1)
        {
            int top = st.top();
            st.pop();
            vis[top] = 0;
            if(top == x) break; 
        }
    }
}

int main()
{
    while(cin >> n >> m, n + m)
    {
        init();

        while(m -- )
        {
            cin >> u >> v;
            add(u, v);
        }
        for(int i = 1; i <= n; i ++ )
            if(!dfn[i])
                Tarjan(i);  

        if(ans == 1)
            cout << "Yes" << endl;
        else 
            cout << "No" << endl;
    }
    return 0;
}

写法2：+ vector

1. init 中 n -> n + 1

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

const int N = 100010;

int n, m;
int u, v, w;
int ans;
int head[N], tot;
int dfn[N], low[N], cnt;
bool vis[N];

struct Edge
{
    int v, nxt, w;
    Edge(int v, int nxt, int w) : v(v), nxt(nxt), w(w) {}
};

vector <Edge> edge[N << 1];
stack <int> st;

void init()
{
    tot = 1;
    cnt = ans = 0;
    for(int i = 1; i <= n + 1; i ++ )
        head[i] = dfn[i] = low[i] = vis[i] = 0, edge[i].clear();
    while(st.size()) st.pop();
}

void Tarjan(int x)
{
    dfn[x] = low[x] = ++ cnt;
    st.push(x);
    vis[x] = 1;
    for(int i = head[x]; i; i = edge[i][0].nxt)
    {
        int v = edge[i][0].v;
        if(!dfn[v])
        {
            Tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if(vis[v])
            low[x] = min(low[x], dfn[v]);
    } 

    if(low[x] == dfn[x])
    {
        ans ++ ;
        while(1)
        {
            int top = st.top();
            st.pop();
            vis[top] = 0;
            if(top == x) break; 
        }
    }
}

int main()
{
    while(cin >> n >> m, n + m)
    {
        init();

        while(m -- )
        {
            cin >> u >> v;
            edge[ ++ tot].push_back(Edge(v, head[u], 0));
            head[u] = tot; 
        }
        for(int i = 1; i <= n; i ++ )
            if(!dfn[i])
                Tarjan(i); 

        if(ans == 1)
            cout << "Yes" << endl;
        else 
            cout << "No" << endl;
    }
    return 0;
}

D.Hdu1455.Sticks

思路

dfs + 剪枝

写法1：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n;
int a[55], vis[55]; 

bool dfs(int len, int l, int cnt)
{
    if(cnt == n && len == l) return true;
    if(len == l) l = 0;

    for(int i = n; i; i -- )
    {
        if(!vis[i] && l + a[i] <= len)
        {
            vis[i] = 1;
            if(dfs(len, l + a[i], cnt + 1))
                return true;
            vis[i] = 0;
            if(l == 0) return false;
            while(a[i] == a[i - 1]) i -- ;  
        }   
    } 
    return false;
}

int main()
{
    while(cin >> n, n)
    {
        int sum = 0;
        for(int i = 1; i <= n; i ++ )
        {
            cin >> a[i];
            sum += a[i]; 
        }
        sort(a + 1, a + n + 1);

        for(int i = a[n]; i <= sum; i ++ )
        {
            if(sum % i) continue;
            memset(vis, 0, sizeof vis);
            if(dfs(i, 0, 0))
            {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
} 

E.Hdu2553.N皇后问题

思路

dfs (+ 位运算) or 打表

写法1：

#include <iostream>

using namespace std;

int n;
int res;

void dfs(int col, int ld, int rd)
{
    if(!col) res ++ ;
    int val = col & ld & rd, pos;
    while(val)
    {
        pos = val & -val; 
        dfs(col ^ pos, (ld ^ pos) << 1 | 1, (rd ^ pos) >> 1 | 1 << n - 1);
        val -= pos;
    }
}

int main()
{
    while(cin >> n, n)
    {
        res = 0;
        int x = (1 << n) - 1;
        dfs(x, x, x);
        cout << res << endl;
    }
    return 0;
}

F.Poj1731.Orders

思路

next_permutation or 实现next_permutation

写法1：sort 对 string 用&

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

string s;

int main()
{
    cin >> s;
    sort(&s[0], &s[0] + s.size());
    do
    {
        cout << s << endl;
    }while(next_permutation(&s[0], &s[0] + s.size()));
    return 0;
}

G.Hdu1312.Red and Black

思路

dfs + bfs

写法1：dfs

#include <iostream>
#include <cstring>

using namespace std;

int n, m;
int sx, sy;
int ans;
char g[22][22];
bool vis[22][22];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void init()
{
    ans = 0;    
    memset(vis, 0, sizeof vis);
}

void dfs(int x, int y)
{
    ans ++ ;
    for(int i = 0; i < 4; i ++ )
    {
        int xx = x + dx[i], yy = y + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] != '#' && !vis[xx][yy])
        {
            vis[xx][yy] = 1;
            dfs(xx, yy);
        }
    }
}

int main()
{
    while(cin >> m >> n, n + m)
    {
        init();
        for(int i = 1; i <= n; i ++ ) cin >> g[i] + 1;

        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )
                if(g[i][j] == '@')
                    sx = i, sy = j;
        vis[sx][sy] = 1;
        dfs(sx, sy);
        cout << ans << endl;
    }
    return 0;
}

写法2：bfs

H.计蒜客.T1735

思路

next_permutation

写法1：用printf

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int a[11];

void init()
{
    for(int i = 1; i <= 9; i ++ )
        a[i] = i;
}

int main()
{
    init();
    cin >> n;
    do
    {
        for(int i = 1; i <= n; i ++ )
            printf("%5d", a[i]);
        printf("\n");
    }while(next_permutation(a + 1, a + n + 1));
    return 0;
}

I.Hdu2717.Catch That Cow

思路

bfs + queue

写法1：

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 100010;

int n, k;
bool vis[N];

struct node
{
    int x, time;
};

queue <node> q;

void init()
{
    memset(vis, 0, sizeof vis);
    while(q.size()) q.pop();
}

int bfs()
{
    node now, nxt;
    now.x = n;
    now.time = 0;
    vis[n] = 1;
    q.push(now);
    while(q.size()) 
    {
        now = q.front();
        q.pop();
        if(now.x == k) 
            return now.time;
        for(int i = 0; i < 3; i ++ )
        {
            if(i == 0)
                nxt.x = now.x - 1;
            else if(i == 1)
                nxt.x = now.x + 1;
            else
                nxt.x = now.x * 2;
            if(nxt.x < 0 || nxt.x > N || vis[nxt.x]) continue;
            nxt.time = now.time + 1;
            vis[nxt.x] = 1;
            q.push(nxt);
        }
    }
}

int main()
{
    while(cin >> n >> k)
    {
        init();
        if(n >= k) 
            cout << n - k << endl;
        else
            cout << bfs() << endl;  
    }   
    return 0;
} 

J.Poj1321.棋盘问题

思路

dfs(i)

写法

#include <iostream>
#include <cstring>

using namespace std;

int n, k;
int ans, cnt;
char g[11][11];
bool vis[11];

void init()
{
    ans = cnt = 0;
    memset(vis, 0, sizeof vis);
}

void dfs(int i)
{
    if(cnt == k)
    {
        ans ++ ;
        return ;
    }
    if(i > n) return ;

    for(int j = 1; j <= n; j ++ )
    {
        if(g[i][j] == '#' && !vis[j])
        {
            cnt ++ ;
            vis[j] = 1;
            dfs(i + 1);
            cnt -- ;
            vis[j] = 0;
        }
    }
    dfs(i + 1);
}

int main()
{
    while(cin >> n >> k, n != -1 && k != -1)
    {
        init();
        for(int i = 1; i <= n; i ++ ) cin >> g[i] + 1;

        dfs(1);
        cout << ans << endl;
    }
    return 0;
}

K.Hdu1175.连连看

思路

bfs + queue

写法1：紧卡时间

1. g[ex][ey] -/-> 0(WA)
2. 剪枝不能在bfs(TLE)

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int n, m;
int t; 
int sx, sy, ex, ey;
int g[1010][1010];
bool vis[1010][1010];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

struct node
{
    int x, y, k;
};

queue <node> q;

void init()
{
    memset(vis, 0, sizeof vis);
    while(q.size()) q.pop();
}

bool bfs()
{
    node now, nxt, tmp;
    now.x = sx, now.y = sy, now.k = -1;
    vis[sx][sy] = 1;
    q.push(now);
    while(q.size())
    {
        now = q.front();
        q.pop();
        if(now.k > 2) continue;
        if(now.x == ex && now.y == ey && now.k <= 2) return true;
        for(int i = 0; i < 4; i ++ )
        {
            nxt.x = now.x + dx[i], nxt.y = now.y + dy[i];
            while(nxt.x >= 1 && nxt.x <= n && nxt.y >= 1 && nxt.y <= m && (!g[nxt.x][nxt.y] || nxt.x == ex && nxt.y == ey))
            {
                if(!vis[nxt.x][nxt.y])
                {
                    nxt.k = now.k + 1;
                    vis[nxt.x][nxt.y] = 1;
                    q.push(nxt);
                }
                tmp.x = nxt.x + dx[i], tmp.y = nxt.y + dy[i];
                nxt = tmp;
            }
        }
    }
    return false;
}

int main()
{
    while(cin >> n >> m, n + m)
    {
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )
                cin >> g[i][j];
        cin >> t;
        while(t -- )
        {
            init();
            bool flg;
            scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
            if(!g[sx][sy] || !g[ex][ey] || g[sx][sy] != g[ex][ey] || sx == ex && sy == ey)  
                flg = 0;
            else 
                flg = bfs();
            if(flg)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
    }
    return 0;
}

写法2：time2 < time1 / 4 (2371ms)

1. g[ex][ey] -/-> 0(WA)
2. 剪枝较1可以在bfs(time2不变)

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int n, m;
int t;
int sx, sy, ex, ey;
int g[1010][1010];
int vis[1010][1010];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

struct node
{
    int x, y, k, d;
};

queue <node> q;

void init()
{
    memset(vis, 127, sizeof vis);
    while(q.size()) q.pop();
}

bool bfs()
{
    if(!g[sx][sy] || !g[ex][ey] || g[sx][sy] != g[ex][ey] || (sx == ex && sy == ey)) return false;
    node now, nxt;
    now.x = sx, now.y = sy, now.k = -1, now.d = -1;
    q.push(now);
    while(q.size())
    {
        now = q.front();
        q.pop();
        if(now.x == ex && now.y == ey && now.k <= 2)    
            return true;            
        for(int i = 0; i < 4; i ++ )
        {
            nxt = now;
            nxt.x += dx[i], nxt.y += dy[i];
            if(nxt.x >= 1 && nxt.x <= n && nxt.y >= 1 && nxt.y <= m && (!g[nxt.x][nxt.y] || nxt.x == ex && nxt.y == ey))
            {
                if(nxt.d != i)
                {
                    nxt.d = i;
                    nxt.k += 1;
                }
                if(nxt.k > 2) continue;
                if(nxt.k <= vis[nxt.x][nxt.y])
                {
                    vis[nxt.x][nxt.y] = nxt.k;
                    q.push(nxt);    
                }
            }
        }
    }
    return false;
}

int main()
{
    while(cin >> n >> m, n + m)
    {
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )
                cin >> g[i][j];

        cin >> t;
        while(t -- )
        {
            init(); 
            scanf("%d %d %d %d", &sx, &sy, &ex, &ey); 
            if(bfs())
                cout << "YES" << endl;
            else 
                cout << "NO" << endl;
        }
    }
    return 0;
}

L.Hdu1241.Oil Deposits

思路

dfs + 染色

写法1：

#include <iostream>
#include <cstring>

using namespace std;

int n, m;
int ans;
char g[110][110];
int vis[110][110];
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

void init()
{
    ans = 0;
    memset(vis, 0, sizeof vis);
}

void dfs(int x, int y)
{
    for(int i = 0; i < 8; i ++ )
    {
        int xx = x + dx[i], yy = y + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] != '*' && !vis[xx][yy])
        {
            vis[xx][yy] = ans;
            dfs(xx, yy);
        }
    }
}

int main()
{
    while(cin >> n >> m, n + m)
    {
        init();
        for(int i = 1; i <= n; i ++ ) cin >> g[i] + 1;
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )
                if(g[i][j] == '@' && !vis[i][j])
                {
                    ans ++ ;
                    vis[i][j] = ans;
                    dfs(i, j);
                }
        cout << ans << endl;
    }
    return 0;
}

M.Poj3984.迷宫问题

思路

bfs + queue + dfs(输出坐标)

写法1：

#include <iostream>
#include <queue>

using namespace std;

int g[6][6];
bool vis[6][6];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

struct node
{
    int x, y;
}pre[6][6], tmp;

queue <node> q;

void init()
{
    tmp.x = tmp.y = 4;
}

void bfs()
{
    node now, nxt;
    now.x = now.y = 0;
    vis[0][0] = 1;
    q.push(now);
    while(q.size())
    {
        now = q.front();
        q.pop();
        if(now.x == 4 && now.y == 4) return ;
        for(int i = 0; i < 4; i ++ )
        {
            nxt = now;
            nxt.x += dx[i], nxt.y += dy[i];
            if(nxt.x >= 0 && nxt.x <= 4 && nxt.y >= 0 && nxt.y <= 4 && !g[nxt.x][nxt.y] && !vis[nxt.x][nxt.y])
            {
                vis[nxt.x][nxt.y] = 1;
                q.push(nxt);
                pre[nxt.x][nxt.y] = now;
            }
        }
    }
}

void dfs(node now)
{
    if(now.x == 0 && now.y == 0)
    {
        cout << "(" << 0 << ", " << 0 << ")" << endl;
        return ;
    }
    dfs(pre[now.x][now.y]);
    cout << "(" << now.x << ", " << now.y << ")" << endl;
}

int main()
{
    init(); 
    for(int i = 0; i < 5; i ++ )
        for(int j = 0; j < 5; j ++ )
            cin >> g[i][j];
    bfs();
    dfs(tmp);
    return 0;
}

N.Hdu1253.胜利大逃亡

思路

bfs + queue

写法1：

1. scanf
2. 剪枝 l + n + m - 3 > time

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int T;
int l, n, m, time;
int g[55][55][55];
bool vis[55][55][55];
int dx[] = {0, 1, 0, -1, 0, 0};
int dy[] = {1, 0, -1, 0, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};

struct node
{
    int x, y, z;
    int t;
};

queue <node> q;

void init()
{
    memset(vis, 0, sizeof vis);
    while(q.size()) q.pop();
}

int bfs()
{
    if(l + n + m - 3 > time) return -1;
    node s, t;
    s.x = s.y = s.z = 1, s.t = 0;
    vis[1][1][1] = 1;
    q.push(s);
    while(q.size())
    {
        s = q.front();
        q.pop();
        if(s.t > time) continue;
        if(s.z == l && s.x == n && s.y == m)
        {
            if(s.t <= time)
                return s.t; 
            else
                return -1;
        }
        for(int i = 0; i < 6; i ++ )
        {
            t = s;
            t.x += dx[i], t.y += dy[i], t.z += dz[i];
            if(t.z >= 1 && t.z <= l && t.x >= 1 && t.x <= n && t.y >= 1 && t.y <= m && !g[t.z][t.x][t.y] && !vis[t.z][t.x][t.y])
            {
                t.t += 1;
                vis[t.z][t.x][t.y] = 1;
                q.push(t);  
            } 
        }
    }   
    return -1;
} 

int main()
{
    cin >> T;
    while(T -- )
    {
        init();
        scanf("%d %d %d %d", &l, &n, &m, &time);
        for(int i = 1; i <= l; i ++ )
            for(int j = 1; j <= n; j ++ )
                for(int k = 1; k <= m; k ++ )
                    scanf("%d", &g[i][j][k]);
        cout << bfs() << endl; 
    }
    return 0;
}

O.Hdu1495.非常可乐

思路

dfs or 数论(gcd, & 1)

写法1：数论

#include <iostream>

using namespace std;

int s, n, m;

int gcd(int x, int y)
{
    while(y ^= x ^= y ^= x %= y);
    return x;
}

int main()
{
    while(cin >> s >> n >> m, s + n + m)
    {
        s /= gcd(n, m);
        if(s & 1)
            cout << "NO" << endl;
        else
            cout << s - 1 << endl; 
    }
    return 0;
}