HUD/HDOJ 1045 Fire Net(回溯)

题目传送门:

http://acm.hdu.edu.cn/showproblem.php?pid=1045

分析:

将一个N*N的方块依次编号0…N*N-1。
可以从0到N*N-1一直判定,假设当前点可以放大炮,则放上,并继续搜索,然后回溯。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
using namespace std;
 
char map[4][4];
int _max;
int n;
 
bool fun(int x, int y)
{
    // 横向
    for(int i=y-1; i>=0; --i)
    {
        if(map[x][i] == '@')
            return 0;
        if(map[x][i] == 'X')
            break;
    }
    // 竖向
    for(int i=x-1; i>=0; --i)
    {
        if(map[i][y] == '@')
            return 0;
        if(map[i][y] == 'X')
            break;
    }
    return 1;
}
 
int solve(int k, int cnt)
{
    int x, y;
    if(k == n*n)
    {
        if(_max < cnt)
        {
            _max = cnt;
            return 0;
        }
    }
    else
    {
        x = k/n;
        y = k%n;
        if(map[x][y] == '.' && fun(x, y))
        {
            map[x][y] = '@';
            solve(k+1, cnt+1);
            map[x][y] = '.';
        }
        solve(k+1, cnt);
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
    while(cin >> n && n)
    {
        _max = 0;
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                cin >> map[i][j];
        solve(0, 0);
        cout << _max << endl;
    }
    return 0;
}

HDU/HDOJ 1026 Ignatius and the Princess I(BFS广搜)

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1026

此题非常非常经典。

搜索用BFS,队列实现,然后输出路径用栈实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
 
typedef struct Node{
	int x, y, cost;
	int prex, prey;
}Node;
 
int N, M;
char maze[105][105];   // 记录初始输入
Node path[105][105];   // 记录路径
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
// 判断(x, y)是否可行
bool isOK(int x, int y)
{
	if(x>=0 && x<N && y>=0 && y<M && maze[x][y]!='X')
		return 1;
	else
		return 0;
}
 
void Init()
{
    int i, j;
    for(i = 0; i < N; ++i)
        for(j = 0; j < M; ++j)
            path[i][j].cost = -1;
}
 
void backPath(int x, int y)
{
    stack<Node> S;
	Node a, b;
    int cc = 1, tmp;
 
    cout << "It takes " << path[N - 1][M - 1].cost 
		<< " seconds to reach the target position, let me show you the way." << endl;
    a = path[N - 1][M - 1];
    while(1)
    {
        if(a.x == 0 && a.y == 0)
            break;
        S.push(a);
        a = path[a.prex][a.prey];
    }
 
    a = path[0][0];
 
    while(!S.empty())
    {
        b = S.top();
        S.pop();
        if(maze[b.x][b.y] == '.')
            cout << cc++ << "s:(" << a.x << "," << a.y << ")->(" << b.x << "," << b.y << ")" << endl;
        else
        {
            cout << cc++ << "s:(" << a.x << "," << a.y << ")->(" << b.x << "," << b.y << ")" << endl;
            tmp = maze[b.x][b.y] - '0';
            while(tmp--)
                cout << cc++ << "s:FIGHT AT (" << b.x << "," << b.y << ")" <<endl;
        }
        a = b;
    }
    cout<<"FINISH"<<endl;
}
 
 
int BFS(int x, int y)
{
	queue<Node> Q;
	Node a, b;
	a.x = a.y = a.cost = a.prex = a.prey = 0;
	if(maze[0][0] != '.')
		a.cost = maze[0][0] - '0';
	path[0][0] = a;
	Q.push(a);
 
	while(!Q.empty())
	{
		a = Q.front();
		Q.pop();
		for(int i=0; i<4; ++i)
		{
			b.x = a.x + dir[i][0];
			b.y = a.y + dir[i][1];
			if(!isOK(b.x, b.y))
				continue;
			if(maze[b.x][b.y] == '.')
				b.cost = a.cost + 1;
			else
				b.cost = a.cost + maze[b.x][b.y]-'0' + 1;
			if(b.cost < path[b.x][b.y].cost || path[b.x][b.y].cost == -1)
            {
                b.prex = a.x; 
				b.prey = a.y;
                path[b.x][b.y] = b;
                Q.push(b);
            }
		}
	}
    if(path[N - 1][M - 1].cost == -1)
    {
        cout << "God please help our poor hero." << endl;
        cout << "FINISH" << endl;
        return 0;
    }
	backPath(N-1, M-1);
}
 
 
int main()
{
	//freopen("input.txt", "r", stdin);
	while(cin >> N >> M)
	{
		memset(maze, 0, sizeof(maze));
		for(int i=0; i<N; ++i)
			for(int j=0; j<M; ++j)
				cin >> maze[i][j];
		Init();
		BFS(0, 0);
	}
	return 0;
}

HDU/HDOJ 1969 Pie

传送门:

http://acm.hdu.edu.cn/showproblem.php?pid=1969

分析:二分搜索

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
 
double pie[10005];
int T, N, F;
double PI = acos(-1.0);
 
bool test(double x)
{
    int cnt = 0;
    for(int i=1; i<=N; ++i)
        cnt += int(pie[i]/x);
    if(cnt >= F+1)
        return 1;
    else
        return 0;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> T;
    double rad;
    double sum;
    while(T--)
    {
        cin >> N >> F;
        sum = 0.0;
        for(int i=1; i<=N; ++i)
        {
            cin >> rad;
            pie[i] = rad*rad*PI;
            sum += pie[i];
        }
        double l = 0.0;
        double r = sum/(F+1);
        double mid;
        while(r-l > 1e-6)
        {
            mid = (l+r)/2.0;
            if(test(mid))
                l = mid;
            else
                r = mid;
        }
        cout << fixed << setprecision(4) << mid << endl;
    }
}

HDOJ 1253 胜利大逃亡

题目传送门:
http://acm.hdu.edu.cn/showproblem.php?pid=1253

话说这题似乎是入门级的BFS。。。
只不过由一般的二维转变成了三维,所以搜索方向由上下左右变成了上下左右前后。
另外,这里要注意剪枝,虽然没剪枝也可以过,但是剪枝后可以减少近一半的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// HDOJ 1253
// Author: Tanky Woo
// BFS
 
#include <iostream>
#include <queue>
using namespace std;
 
int Castle[51][51][51];  // the castle
int vis[51][51][51];  // have visited
int dir[6][3]={       // direction
    {0, 0, 1},   // up
    {0, 0, -1},  // down
    {1, 0, 0},   // left
    {-1, 0, 0},  // right
    {0, 1, 0},   // front
    {0, -1, 0},  // after
};
 
int A, B, C, T, nCases;
 
typedef struct node
{
    int x, y, z;
    int step;
}Node;
 
void BFS()
{
    memset(vis, 0, sizeof(vis));
    vis[0][0][0] = 1;
    queue<Node> Que;
    Node pre, last;
    pre.x = pre.y = pre.z = pre.step = 0;
    Que.push(pre);
    while(!Que.empty())
    {
        pre = Que.front();
        Que.pop();
        if(pre.step > T)   // 剪枝一
            break;
        if(abs(A-1-pre.x) + abs(B-1-pre.y) + abs(C-1-pre.z) > T)    //剪枝二,这个剪枝使时间减少了500ms。
            break;
        if(pre.x==A-1 && pre.y==B-1 && pre.z==C-1)
        {
            printf("%d\n", pre.step);
            return;
        }
        for(int i=0; i<6; ++i)
        {
            last.x = pre.x+dir[i][0];
            last.y = pre.y+dir[i][1];
            last.z = pre.z+dir[i][2];
            last.step = pre.step+1;
            if(last.x>=0 && last.x<A 
                && last.y>=0 && last.y<B
                && last.z>=0 && last.z<C
                && !vis[last.x][last.y][last.z]
                && Castle[last.x][last.y][last.z]!=1)
                {
                    vis[last.x][last.y][last.z] = 1;
                    Que.push(last);
                }
        }
    }
    printf("-1\n");
}
 
 
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &nCases);
    while(nCases--)
    {
        scanf("%d %d %d %d", &A, &B, &C, &T);
        for(int i=0; i<A; ++i)  //
            for(int j=0; j<B; ++j)  //
                for(int k=0; k<C; ++k)   //
                    scanf("%d", &Castle[i][j][k]);
        BFS();
    }
    return 0;
}

HDOJ 1239 Calling Extraterrestrial Intelligence Again

题目传送门:
http://acm.hdu.edu.cn/showproblem.php?pid=1239

搜索的题目。
我感觉这题直接判断是否满足条件就OK了,为何HDOJ的课件上还说用剪枝?谁能告诉我?
先分析:得到:2<= p,q <=10000。 再用筛选法打表求出10000以内的素数, 接着就是搜索遍历了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;
__int64 m, a, b, p, q;
__int64 _maxa, _maxb, _max;
 
bool vis[10001];
int prime[5000];
int main()
{
    memset(vis, 0, sizeof(vis));
    for(int i = 2; i <= 100; i++)
        for(int j = i*2; j <= 10000; j += i)
            vis[j] = 1;
    int n=0;
    for(int i=2; i<=10000; ++i)
        if(vis[i] == 0)
            prime[n++] = i;
    bool flag=0;
    while(scanf("%I64d %I64d %I64d", &m, &a, &b) && (a+b+m))
    {
        _max = _maxa = _maxb = 0;
        flag = 0;
        for(int i=n-1; i>=0; --i)
        {
            for(int j=n-1; j>=i; --j)
                if((prime[j]*prime[i] <= m) && (prime[j]*prime[i]>_max) && (double)prime[i]/prime[j]>=((double)a/b))
                {
                    _max = prime[j]*prime[i];
                    _maxa = i;
                    _maxb = j;
                }
        }
        printf("%d %d\n", prime[_maxa], prime[_maxb]);
    }
    return 0;
}