poj1321 DFS水

2011年6月03日 22:09

 

棋盘问题
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 11335   Accepted: 5563

Description

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

Input

输入含有多组测试数据。 
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 
当为-1 -1时表示输入结束。 
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。 

Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

Sample Input

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

Sample Output

2
1

 

#include<cstdio>
#include<cstring>
int n,k;
int i;
int j;
char board[12][12];
int pos[12];
int cnt;
void DFS(int row,int num)
{
    if(num==0)
    {
        cnt++;
        return;
    }
    if(row>=n) return;
    for(int l=0; l<n; l++)
    {
        if(pos[l]!=1&&board[row][l]=='#')
        {
            pos[l]=1;
            DFS(row+1,num-1);
            pos[l]=0;
        }
    }
    DFS(row+1,num);
}
int main()
{
    scanf("%d%d",&n,&k);
    while(n!=-1&&k!=-1)
    {
        for(i=0; i<n; i++)
            scanf("%s",board[i]);
        cnt=0;
        memset(pos,0,sizeof(pos));
        DFS(0,k);
        printf("%d\n",cnt);
        scanf("%d%d",&n,&k);
    }
    return 0;
}

 

Posted by WARush Filed in poj的挣扎 Tagged by DFS poj acm 水 Comments[4]

buaa通向女友之路~水~模板

2010年10月12日 02:01

 

吉大模板A的水，不知道ab同学怎么能tle的。。。。dijkstra
#include <cstdlib>
#include <limits>
#include <ctime>
#include <memory>
#include <cmath>
#include <functional>
#include <numeric>
 
#include <cstdio>
#include <iostream>
#include <fstream>
//#include <strstream>
 
#include <algorithm>
#include <iterator>
#include <map>
#include <set>
//#include <ext/hash_map>
//#include <ext/hash_set>
//#include <hash_map>
//#include <hash_set>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
 
using namespace std;
 
/*==================================================*\
| Dijkstra O(E * log E)
| INIT: 调用init(nv, ne)读入边并初始化;
| CALL: dijkstra(n, src); dist[i]为src到i的最短距离
\*==================================================*/
#define typec int // type of cost
#define V 10001
#define E 100001
const typec inf = 0x3f3f3f3f; // max of cost
typec cost[E], dist[V];
int e, pnt[E], nxt[E], head[V], prev[V], vis[V];
 
struct qnode {
    int v;
    typec c;
 
    qnode(int vv = 0, typec cc = 0) : v(vv), c(cc) {
    }
 
    bool operator<(const qnode & r) const {
        return c > r.c;
    }
};
 
void dijkstra(int n, const int src) {
    qnode mv;
    int i, j, k, pre;
    priority_queue<qnode> que;
    vis[src] = 1;
    dist[src] = 0;
    que.push(qnode(src, 0));
    for (pre = src, i = 1; i < n; i++) {
        for (j = head[pre]; j != -1; j = nxt[j]) {
            k = pnt[j];
            if (vis[k] == 0 &&
                    dist[pre] + cost[j] < dist[k]) {
                dist[k] = dist[pre] + cost[j];
                que.push(qnode(pnt[j], dist[k]));
                prev[k] = pre;
            }
        }
        while (!que.empty() && vis[que.top().v] == 1)
            que.pop();
        if (que.empty()) break;
        mv = que.top();
        que.pop();
        vis[pre = mv.v] = 1;
    }
}
 
inline void addedge(int u, int v, typec c) {
    pnt[e] = v;
    cost[e] = c;
    nxt[e] = head[u];
    head[u] = e++;
}
 
void init(int nv, int ne) {
    int i, u, v;
    typec c;
    e = 0;
    memset(head, -1, sizeof (head));
    memset(vis, 0, sizeof (vis));
    memset(prev, -1, sizeof (prev));
    for (i = 0; i < nv; i++) dist[i] = inf;
    for (i = 0; i < ne; ++i) {
        scanf("%d%d%d", &u, &v, &c); // %d: type of cost
        //printf("%d%d%d\n", u, v, c);
        u--;
        v--;
        addedge(u, v, c); // vertex: 0 ~ n-1, 单向边
        //addedge(v, u, c);
    }
}
 
int main() {
    int m, n;
    int s,t;
    while(cin >> n >> m) {
        init(n, m);
        //printf("%d", e);
        cin>>s>>t;
        dijkstra(n, s-1);
        cout << dist[t-1] << endl;
    }
    return 0;
}

Posted by WARush Filed in ACM杂题不解释 Tagged by dijkstra 水 ACM Comments[4]