N皇后问题

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 30   Accepted Submission(s) : 13

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

1
8
5
0

Sample Output

1
92
10

Author

cgf

Source

2008 HZNU Programming Contest
 
思路：这题难点就是时间问题，但是看见数据很小，所以我就本地跑一下数据，然后放数组里面就好了（逃了逃了~）
  
#include<iostream>
using namespace std;
int main(){
    int n;
    int ans[11] = {0,1,0,0,2,10,4,40,92,352,724};
    while (cin>>n && n){cout << ans[n] << endl;}
    return 0;
}

 

 

Oil Deposits

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 39   Accepted Submission(s) : 20

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid. 

Input

The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*', representing the absence of oil, or `@', representing an oil pocket.

Output

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

Sample Input

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5 
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

Sample Output

0
1
2
2

Source

Mid-Central USA 1997
 
思路：很简单的搜索题，bfs和dfs都可以实现，不过注意一下，每个油田的范围是上下左右和斜上斜下的8个格子，而不是简单的上下左右四个格子。
  
#include<iostream>
#include<cstdio>
using namespace std;
char map[105][105];
int ans;
int n, m;
int after[8][2]= { {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1} };
void dfs(int x, int y)
{
    int tx, ty;
    for (int k = 0; k <= 7; k++) {
        tx = x + after[k][0];
        ty = y + after[k][1];
        if (tx<1 || tx>n || ty<1 || ty>m) { continue; }
        if (map[tx][ty] == '@')
        {
            map[tx][ty] = '*';
            dfs(tx, ty);
        }
    }
}

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF && n)
    {
        ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> map[i][j];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (map[i][j] == '@')
                {
                    ans++;
                    map[i][j] = '*';
                    dfs(i, j);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

 

 

Sudoku Killer

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 11   Accepted Submission(s) : 7

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

自从2006年3月10日至11日的首届数独世界锦标赛以后，数独这项游戏越来越受到人们的喜爱和重视。
据说，在2008北京奥运会上，会将数独列为一个单独的项目进行比赛，冠军将有可能获得的一份巨大的奖品———HDU免费七日游外加lcy亲笔签名以及同hdu acm team合影留念的机会。
所以全球人民前仆后继，为了奖品日夜训练茶饭不思。当然也包括初学者linle，不过他太笨了又没有多少耐性，只能做做最最基本的数独题，不过他还是想得到那些奖品，你能帮帮他吗？你只要把答案告诉他就可以，不用教他是怎么做的。

数独游戏的规则是这样的：在一个9x9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。比如有这样一个题，大家可以仔细观察一下，在这里面每行、每列，以及每个3x3的方格都包含1-9这九个数字。

例题：


答案：

Input

本题包含多组测试，每组之间由一个空行隔开。每组测试会给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，问号（?）表示需要你填的数。

Output

对于每组测试，请输出它的解，同一行相邻的两个数用一个空格分开。两组解之间要一个空行。
对于每组测试数据保证它有且只有一个解。

Sample Input

7 1 2 ? 6 ? 3 5 8
? 6 5 2 ? 7 1 ? 4
? ? 8 5 1 3 6 7 2
9 2 4 ? 5 6 ? 3 7
5 ? 6 ? ? ? 2 4 1
1 ? 3 7 2 ? 9 ? 5
? ? 1 9 7 5 4 8 6
6 ? 7 8 3 ? 5 1 9
8 5 9 ? 4 ? ? 2 3

Sample Output

7 1 2 4 6 9 3 5 8
3 6 5 2 8 7 1 9 4
4 9 8 5 1 3 6 7 2
9 2 4 1 5 6 8 3 7
5 7 6 3 9 8 2 4 1
1 8 3 7 2 4 9 6 5
2 3 1 9 7 5 4 8 6
6 4 7 8 3 2 5 1 9
8 5 9 6 4 1 7 2 3

思路：这题的输出格式纯粹就是拿来恶心人的，除了第一组数据和第一组输出结果之间不需要空行外，剩下的数据 每组输入和输出之间都有一个空行！
　　　解题的思路是，用两个数组来保存每行每列已经存在的数，这样在9x9的判断就不需要一个个去搜索。
　　　而3X3的地方就有一个小技巧，可以用 x=x-x%3  y=y-y%3 这样，x和y就会变成每一个数对应的 3X3 的第一个格子的坐标，然后搜索判断就行了。
　　　还有一个小技巧就是可以把每个'？'的坐标单独保存下来，这样就可以直接根据对应的点展开搜索了。
　　
　　
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>

using namespace std;

#define M 10

struct Data//‘？’的坐标
{
    int x, y;
}step[M*M];

int flag;
int cnt;
int Case;
int Map[M][M];
bool book_x[M][M];//判断x行对应的数字是否为true
bool book_y[M][M];//判断y列对应的数组是否为true
char temp;

void init()
{
    flag=cnt = 0;
    memset(book_x, false, sizeof(book_x));
    memset(book_y, false, sizeof(book_y));
}

void GetData()
{
    if (temp == '?') {
        Map[0][0] = 0;
        step[cnt].x = step[cnt].y = 0;
        cnt++;
    }
    else {
        Map[0][0] = temp - '0';
        book_x[0][Map[0][0]] = book_y[0][Map[0][0]] = true;
    }
    for (int i = 1; i < 9; i++) {
        cin >> temp;
        if (temp == '?') {
            Map[0][i] = 0;
            step[cnt].x = 0;
            step[cnt].y = i;
            cnt++;
        }
        else {
            Map[0][i] = temp - '0';
            book_x[0][Map[0][i]] = book_y[i][Map[0][i]] = true;
        }
    }
    for (int i = 1; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> temp;
            if (temp == '?') {
                Map[i][j] = 0;
                step[cnt].x = i;
                step[cnt].y = j;
                cnt++;
            }
            else {
                Map[i][j] = temp - '0';
                book_x[i][Map[i][j]] = book_y[j][Map[i][j]] = true;
            }
        }
    }
    if (Case++) {
        cout << endl;
    }
}

void printf_ans()
{
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 8; j++) {
            printf("%d ", Map[i][j]);
        }
        printf("%d\n", Map[i][8]);
    }
}

bool find(int T, int aim)
{
    if (book_x[step[T].x][aim] || book_y[step[T].y][aim]) {
        return false;
    }
    int x, y;
    x = step[T].x - step[T].x % 3;//对应3X3的第一个格子的x坐标
    y = step[T].y - step[T].y % 3;//对应3X3的第一个格子的y坐标
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (Map[x + i][y + j] == aim) {
                return false;
            }
        }
    }
    return true;
}

void dfs(int num)
{
    if (flag) { return; }
    if (num == cnt) {
        flag = 1;
        printf_ans();
    }
    for (int i = 1; i < 10; i++) {
        if (find(num,i)) {
            Map[step[num].x][step[num].y] = i;
            book_x[step[num].x][i] = book_y[step[num].y][i] = true;
            dfs(num + 1);
            Map[step[num].x][step[num].y] = 0;
            book_x[step[num].x][i] = book_y[step[num].y][i] = false;
        }
    }
}

int main()
{
    while (cin>>temp)
    {
        init();
        GetData();
        dfs(0);
    }
    return 0;
}