基础搜索算法题解(N-R)

#include <cstdio>
#include <cstring>
int n, len, ans;
char s[10];
bool rejected;
bool mark[10], tmark[10];

//当前的和，当前数字的头下标，当前数字的尾下标
void DFS(int sum, int st, int ed)
{
    if(sum > n)
        return;
    int cur = 0;
    for(int i = st; i < ed; i++)
    {
        cur *= 10;
        cur += (s[i] - '0');
    }
    if(ed == len)
    {
        sum += cur;
        if(sum <= n && ans >= 0)
        {
            if(ans < sum)
            {
                ans = sum;
                rejected = false;
                for(int i = 0; i < len; i++)
                    mark[i] = tmark[i];
            }
            else if(sum == ans)
                rejected = true;
        }
        return;
    }
    tmark[ed] = false;
    DFS(sum, st, ed + 1); //不拆
    tmark[ed] = true;
    DFS(sum + cur, ed, ed + 1) ;//拆
}

int main()
{
    int t;
    while(scanf("%d %d", &n, &t) && (n + t))
    {
        rejected = false;
        int tmp = t, sum = 0;
        while(tmp)
        {
            sum += (tmp % 10);
            tmp /= 10;
        }
        if(sum > n)
        {
            printf("error\n");
            continue;
        }
        if(n == t)
        {
            printf("%d %d\n", n, n);
            continue;
        }
        sprintf(s, "%d", t);    
        len = strlen(s);
        ans = 0;
        tmark[0] = true;
        DFS(0, 0, 1);
        if(rejected)
            printf("rejected\n");
        else if(ans > 0)
        {
            printf("%d", ans);
            for(int i = 0; i < len; i++)
            {
                if(mark[i])
                    printf(" ");
                printf("%c", s[i]);
            }
            printf("\n");
        }
    }
}

Description

Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task. 

Input

Output

Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

Source

#include <cstdio>
char s[10];
int num[9][9];
bool flag;

bool ok(int n, int cur) 
{
    int r = n / 9;		//当前行
	int c = n % 9;		//当前列
    for(int j = 0; j < 9; j++)  //枚举列
        if (num[r][j] == cur) 
            return false;
    for(int i = 0; i < 9; i++)  //枚举行
        if (num[i][c] == cur) 
            return false;
	//得到当前所在的子矩阵的第一个元素位置
    int x = r / 3 * 3;	
    int y = c / 3 * 3;
	//枚举子矩阵中的元素
    for(int i = x; i < x + 3; i++)
        for(int j = y; j < y + 3; j++)
            if (num[i][j] == cur) 
                return false;
    return true;
}

void DFS(int n)
{
    if(n > 80 || flag) 
    {
        flag = true;
        return;
    }
	if(num[n / 9][n % 9])//当前位置有数字直接搜索下一位
	{
        DFS(n + 1);
		if(flag)
			return;
	}
    else
    {
        for(int cur = 1; cur <= 9; cur++)  //枚举数字
        {
            if(ok(n, cur)) //若ok则插入
            {
                num[n / 9][n % 9] = cur; 
                DFS(n + 1);
                if(flag) 
                    return;
                num[n / 9][n % 9] = 0; //还原
            }
        }
    }
}

int main()
{   
    int T;
    scanf("%d", &T);
    while(T--)
    {
        flag = false;
        for(int i = 0; i < 9; i++) //得到数独矩阵
		{
			scanf("%s", s);
            for(int j = 0; j < 9; j++)
                num[i][j] = (s[j] - '0');
		}
        DFS(0);  //从第一位开始搜
        for(int i = 0; i < 9; i++)
        {
            for(int j = 0; j < 9; j++)
                printf("%d", num[i][j]);
            printf("\n");      
        }
    }
}

2
A:
B:
4
A:BC
B:ACD
C:ABD
D:BC
4
A:BCD
B:ACD
C:ABD
D:ABC
0

1 channel needed.
3 channels needed.
4 channels needed. 

#include<cstdio>
#include<cstring>
int map[30][30];
int color[30];
int n,col;
bool flag;
char s[30];

bool ok(int i)
{
	//若与i直接相连的各点值均与i点值不同则返回true
    for(int j = 0; j < 26; j++)
	{
		if(!map[i][j])
			continue;
        if(color[i] == color[j])
			return false;
	}
    return true;
}

void dfs(int num)
{
    if(num == n) //若num与n相等，则着色完毕
    {
        flag = true;
        return;
    }
    for(int i = 1; i <= col; i++) //枚举col个数字用来标记
    {
        color[num] = i;			//赋值
        if(ok(num))				//若当前赋值符合条件搜索下一个
			dfs(num + 1);
        color[num] = 0;			//还原
    }
}

int main()
{
    while(scanf("%d", &n) && n)
    {
		flag = false;
        memset(map, 0, sizeof(map));
        for(int i = 0; i < n; i++) //构图
        {
            scanf("%s", s);
			int len = strlen(s);
            for(int j = 2; j < len; j++)
                map[i][s[j]-'A'] = map[s[j]-'A'][i] = 1;
        } 
        for(col = 1; col <= 4; col++) //根据四色定理枚举1-4，代表用几个数字可以标记完
        {
            dfs(0); //从第一个字母开始搜索赋值
            if(flag)
				break;
        }
        if(col == 1) 
			printf("1 channel needed.\n");
        else 
			printf("%d channels needed.\n", col);
    }
    return 0;
}

Q题 图的深度优先遍历序列

<span style="font-size:14px;">#include <cstdio>
 #include <cstring>
 int map[25][25];
 bool vis[25];
 int n, e;

 void DFS(int a)
 {
     vis[a] = true;
     printf("%d ", a);
     for(int i = 0; i < n; i++)
         if(map[a][i] && !vis[i])
             DFS(i);
 }

 int main()
 {
     int x, y;
     scanf("%d %d", &n, &e);
     memset(map, 0, sizeof(map));
     memset(vis, false, sizeof(vis));
     for(int i = 0; i < e; i++)
     {
         scanf("%d %d", &x, &y);
         map[x][y] = 1;
         map[y][x] = 1;
     }
     for(int i = 0; i < n; i++)
     {
         for(int j = 0; j < n; j++)
             printf("%d ", map[i][j]);
         printf("\n");
     }
     for(int i = 0; i < n; i++)
         if(!vis[i])
             DFS(i);
     printf("\n");
 }</span>