分类目录归档:搜索

洛谷10月月赛R1·浴谷八连测R1·提高组 SAC E#1 – 一道大水题 Knight

洛谷题号:P3930
2017.10.20更新:
有人在洛谷上指出了本程序的错误:测试样例:
5
….X
…..
…..
….B
..O..
存在一种4步的解法。
….4
…..
…3.
….1
..2..
但程序会输出-1。
经过检查,所给出的测试样例中四步解法经过了之前已经经过的点,这种情况是我的程序所无法处理的。因此我的程序存在漏洞,目前还没有想到什么好办法解决。。
原文章:
本来没想着这题能得分,结果这题月赛时竟然80分,后来出题人说有两个点错了,重测就100了。。。/捂脸

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
int n;
char arr[60][60]; //存放棋子
bool attack[2][60][60]; //某点是否可以被攻击(第一维没有用处,只用了第一维的1)
int dp[60][60];
int O_x, O_y, X_x_pos, X_y_pos;
int K_x[8] = {1,2,2,1,-1,-2,-2,-1};
int K_y[8] = {2,1,-1,-2,-2,-1,1,2};
int X_x[8] = {-1,0,1,-1,1,-1,0,1};
int X_y[8] = {-1,-1,-1,0,0,1,1,1};
inline void render(int x, int y, int no){ //针对坐标为(x,y)的棋子在attack数组中绘制出攻击范围
    switch (arr[x][y]){
    case 'C'://城堡
        for (int i = x + 1; i <= n; i++){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = x - 1; i >= 1; i--){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = y + 1; i <= n; i++){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        for (int i = y - 1; i >= 1; i--){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        break;
    case 'K'://骑士
        for (int i = 0; i < 8; i++){
            if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
                attack[no][x + K_x[i]][y + K_y[i]] = true;
            }
        }
        break;
    case 'B'://主教
        for (int i = 1; y - i > 0 && x + i <= n; i++){//向右上角移动
            if (arr[x + i][y - i] == '.')attack[no][x + i][y - i] = true;
            else {
                attack[no][x + i][y - i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x + i <= n; i++){//向右下角移动
            if (arr[x + i][y + i] == '.')attack[no][x + i][y + i] = true;
            else{
                attack[no][x + i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x - i > 0; i++){//向左下角移动
            if (arr[x - i][y + i] == '.')attack[no][x - i][y + i] = true;
            else{
                attack[no][x - i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y - i > 0 && x - i > 0; i++){//向左上角移动
            if (arr[x - i][y - i] == '.')attack[no][x - i][y - i] = true;
            else{
                attack[no][x - i][y - i] = true;
                break;
            }
        }
        break;
    case 'Q'://皇后
        //城堡
        for (int i = x + 1; i <= n; i++){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = x - 1; i >= 1; i--){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = y + 1; i <= n; i++){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        for (int i = y - 1; i >= 1; i--){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        //主教
        for (int i = 1; y - i > 0 && x + i <= n; i++){//向右上角移动
            if (arr[x + i][y - i] == '.')attack[no][x + i][y - i] = true;
            else {
                attack[no][x + i][y - i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x + i <= n; i++){//向右下角移动
            if (arr[x + i][y + i] == '.')attack[no][x + i][y + i] = true;
            else{
                attack[no][x + i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x - i > 0; i++){//向左下角移动
            if (arr[x - i][y + i] == '.')attack[no][x - i][y + i] = true;
            else{
                attack[no][x - i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y - i > 0 && x - i > 0; i++){//向左上角移动
            if (arr[x - i][y - i] == '.')attack[no][x - i][y - i] = true;
            else{
                attack[no][x - i][y - i] = true;
                break;
            }
        }
        break;
    case 'X'://国王
        for (int i = 0; i < 8; i++){
            if (x + X_x[i]>0 && x + X_x[i] <= n&&y + X_y[i] > 0 && y + X_y[i] <= n){
                attack[no][x + X_x[i]][y + X_y[i]] = true;
            }
        }
        break;
    case 'P'://普通士兵
        if (x - 1 > 0 && x - 1 <= n&&y + 1 > 0 && y + 1 <= n){
            attack[no][x - 1][y + 1] = true;
        }
        if (x + 1 > 0 && x + 1 <= n&&y + 1 > 0 && y + 1 <= n){
            attack[no][x + 1][y + 1] = true;
        }
        break;
    }
}
inline void render_all(){//将地图上的所有点全部重绘
    memset(attack, false, sizeof(attack));
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            switch (arr[i][j]){
            case 'O'://标记好白骑士的起始点
                O_x = i;
                O_y = j;
                break;
            case '.':
            case '\0':
                break;
            case 'X'://黑国王的终止点
                X_x_pos = i;
                X_y_pos = j;
            default:
                render(i, j, 1);
            }
        }
    }
}
void dfs(int x, int y,int step){//记忆化dfs
    if (x <= 0 || y <= 0 || x > n || y > n)return; //超出边界的情况
    if (arr[x][y] == 'X'){ //dfs到了黑国王
        if (step < dp[x][y])dp[x][y] = step;
        return;
    }
    if (attack[1][x][y])return; //刚跳到坐标x,y就被攻击了
    if (step>=dp[x][y])return; //注意,这里是重点,也是为什么DFS不会超时的原因,因为我写的这个DFS记忆化不满足无后效性,所以只要走到一点后,当前步数大于之前走到过这里的最小步数就可以退出了。
    dp[x][y] = step;
    if (arr[x][y] != '.'){ //该格子上有棋子
        char ch = arr[x][y];
        arr[x][y] = '.';
        render_all(); //把棋子吃掉以后重新绘制攻击情况
        for (int i = 0; i < 8; i++){
            if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
                dfs(x + K_x[i], y + K_y[i], step + 1);
            }
        }
        arr[x][y] = ch; //回溯
        render_all();
    }
    else{ //该格子上无棋子
        for (int i = 0; i < 8; i++){
            if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
                dfs(x + K_x[i], y + K_y[i], step + 1);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false); //加快cin速度
    while (cin >> n){ //多组数据
        memset(arr, 0, sizeof(arr));
        memset(attack, false, sizeof(attack));
        memset(dp, 0x7f, sizeof(dp));
        for (int i = 1; i <= n; i++){
            cin >> arr[i] + 1;
        }
        render_all(); //先进行整幅地图攻击情况的绘制
        dfs(O_x, O_y, 0);
        if (dp[X_x_pos][X_y_pos] == 0x7f7f7f7f){
            cout << -1 << endl;
        }
        else{
            cout << dp[X_x_pos][X_y_pos] << endl;
        }
    }
    return 0;
}

洛谷/USACO 魔板 Magic Squares

洛谷题号:P2730
THUOJ上也有这道题目,题目输入输出格式略微有不同,基本原理相同。但是THUOJ不能使用任何数据结构,全部都要自己写。

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
struct status{
    int arr[9];
};
string s_result;
template <typename T> struct node{
    T data;
    node<T> * next;
};
template <typename T> struct list{
    node<T> * head;
    int _size;
    list(){
        _size = 0;
        head = NULL;
    }
    ~list(){
        node <T> * current = head;
        node <T> * next;
        while (current != NULL){
            next = current->next;
            delete current;
            current = next;
        }
    }
    void insert(T & data){
        _size++;
        node<T> * ptr = new node<T>;
        ptr->data = data;
        ptr->next = head;
        head = ptr;
    }
    bool search(T & target){
        node<T> * ptr = head;
        while (ptr != NULL){
            if (ptr->data == target)return true;
            ptr = ptr->next;
        }
        return false;
    }
};
list<int> hashtable[50021];
inline int h(const int m){
    return (2 * m + 29) % 50021;
}
inline int status2int(status m){
    int t = 0;
    for (int i = 1; i <= 8; i++){
        t *= 10;
        t += m.arr[i];
    }
    return t;
}
inline status int2status(int t){
    status m;
    for (int i = 8; i >= 1; i--){
        m.arr[i] = t % 10;
        t /= 10;
    }
    return m;
}
inline int change(int status_m, char type){
    status m = int2status(status_m);
    int t;
    switch (type){
    case 'A':
        swap(m.arr[1], m.arr[8]);
        swap(m.arr[2], m.arr[7]);
        swap(m.arr[3], m.arr[6]);
        swap(m.arr[4], m.arr[5]);
        break;
    case 'B':
        t = m.arr[4];
        for (int i = 4; i >= 2; i--)m.arr[i] = m.arr[i - 1];
        m.arr[1] = t;
        t = m.arr[5];
        for (int i = 5; i <= 7; i++)m.arr[i] = m.arr[i + 1];
        m.arr[8] = t;
        break;
    case 'C':
        t = m.arr[2];
        m.arr[2] = m.arr[7];
        m.arr[7] = m.arr[6];
        m.arr[6] = m.arr[3];
        m.arr[3] = t;
        break;
    }
    return status2int(m);
}
int BFS(int m){
    queue<int> q;
    queue<int> qi;
    queue<string> qs;
    q.push(12345678);
    qi.push(0);
    qs.push("");
    while (!q.empty()){
        int t = q.front();
        q.pop();
        int time = qi.front();
        qi.pop();
        string str = qs.front();
        qs.pop();
        if (t == m){
            s_result = str;
            return time;
        }
        else if (time > 30){
            continue;
        }
        else{
            int s = change(t, 'A');
            if (!hashtable[h(s)].search(s)){
                hashtable[h(s)].insert(s);
                q.push(s); qi.push(time + 1); qs.push(str + 'A');
            }
            s = change(t, 'B');
            if (!hashtable[h(s)].search(s)){
                hashtable[h(s)].insert(s);
                q.push(s); qi.push(time + 1); qs.push(str + 'B');
            }
            s = change(t, 'C');
            if (!hashtable[h(s)].search(s)){
                hashtable[h(s)].insert(s);
                q.push(s); qi.push(time + 1); qs.push(str + 'C');
            }
        }
    }
    return -1;
}
int main(){
    ios::sync_with_stdio(false);
    status m;
    for (int i = 1; i <= 8; i++){
        cin >> m.arr[i];
    }
    cout << BFS(status2int(m)) << endl;
    cout << s_result << endl;
   
}

洛谷 穿越栅栏 Overfencing

题号:1519

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<list>
#include<functional>
#include<string>
using namespace std;
int w, h, m=0;
char graph[300][300];
bool visited[300][300];
int steps[300][300];
int check_x[5] = {0,1,-1,0,0},
check_y[5] = {0,0,0,1,-1},
step_x[5] = {0,2,-2,0,0},
step_y[5] = {0,0,0,2,-2};
struct node {
    int x, y, step;
    node(int x1,int y1,int step1) {
        x = x1; y = y1; step = step1;
    }
};
bool check(int cx, int cy, int sx, int sy) {
    if (!visited[sx][sy] && graph[cx][cy] == ' '&&sx % 2 == 0 && sy % 2 == 0 && sx < 2 * h + 1 && sx>1 && sy < 2 * w + 1 && sy>1)return true;
    return false;
}
void BFS(int x,int y) {
    int maxstep = 0;
    queue<node> q;
    memset(visited, false, sizeof(visited));
    q.push(node(x, y, 0));
    while (!q.empty()) {
        node t = q.front(); q.pop();
        if (steps[t.x][t.y]> t.step)steps[t.x][t.y] = t.step;
        if (visited[t.x][t.y])continue;
        visited[t.x][t.y] = true;
        for (int i = 1; i <= 4; i++) {
            if (check(t.x + check_x[i], t.y + check_y[i], t.x + step_x[i], t.y + step_y[i]))q.push(node(t.x + step_x[i], t.y + step_y[i], t.step + 1));
        }
    }
}
int main() {
    cin >> w >> h;
    cin.getline(graph[0] + 1, 280);
    memset(steps, 0x7f, sizeof(steps));
    for (int i = 1; i <= 2 * h + 1; i++) {
        cin.getline(graph[i] + 1, 280);
    }
    for (int i = 2; i <= 2 * w; i++) {
        if (graph[1][i] == ' ')BFS(2, i);
        if (graph[2 * h + 1][i] == ' ')BFS(2 * h, i);
    }
    for (int i = 2; i <= 2 * h; i++) {
        if (graph[i][1] == ' ')BFS(i, 2);
        if (graph[i][2 * w + 1] == ' ')BFS(i, 2 * w);
    }
    for (int i = 2; i <= 2 * h; i+=2) {
        for (int j = 2; j <= 2 * w; j += 2) {
            if (steps[i][j] > m&&steps[i][j]!=0x7f7f7f7f)m = steps[i][j];
        }
    }
    cout << m+1 << endl;
}

USACO Section 2.1 PROB The Castle

The Castle
IOI’94 – Day 1
In a stroke of luck almost beyond imagination, Farmer John was sent a ticket to the Irish Sweepstakes (really a lottery) for his birthday. This ticket turned out to have only the winning number for the lottery! Farmer John won a fabulous castle in the Irish countryside.

Bragging rights being what they are in Wisconsin, Farmer John wished to tell his cows all about the castle. He wanted to know how many rooms it has and how big the largest room was. In fact, he wants to take out a single wall to make an even bigger room.

Your task is to help Farmer John know the exact room count and sizes.

The castle floorplan is divided into M (wide) by N (1 <=M,N<=50) square modules. Each such module can have between zero and four walls. Castles always have walls on their “outer edges” to keep out the wind and rain.

Consider this annotated floorplan of a castle:

     1   2   3   4   5   6   7
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#   
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #   
   #---#########---#####---#---#
 4 # ->#   |   |   |   |   #   #   
   ############################# 

#  = Wall     -,|  = No wall
-> = Points to the wall to remove to
     make the largest possible new room

By way of example, this castle sits on a 7 x 4 base. A “room” includes any set of connected “squares” in the floor plan. This floorplan contains five rooms (whose sizes are 9, 7, 3, 1, and 8 in no particular order).

Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall.

The castle always has at least two rooms and always has a wall that can be removed.

PROGRAM NAME: castle

INPUT FORMAT

The map is stored in the form of numbers, one number for each module, M numbers on each of N lines to describe the floorplan. The input order corresponds to the numbering in the example diagram above.

Each module number tells how many of the four walls exist and is the sum of up to four integers:

  • 1: wall to the west
  • 2: wall to the north
  • 4: wall to the east
  • 8: wall to the south

Inner walls are defined twice; a wall to the south in module 1,1 is also indicated as a wall to the north in module 2,1.

Line 1: Two space-separated integers: M and N
Line 2..: M x N integers, several per line.

SAMPLE INPUT (file castle.in)

7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

OUTPUT FORMAT

The output contains several lines:

Line 1: The number of rooms the castle has.
Line 2: The size of the largest room
Line 3: The size of the largest room creatable by removing one wall
Line 4: The single wall to remove to make the largest room possible

Choose the optimal wall to remove from the set of optimal walls by choosing the module farthest to the west (and then, if still tied, farthest to the south). If still tied, choose ‘N’ before ‘E’. Name that wall by naming the module that borders it on either the west or south, along with a direction of N or E giving the location of the wall with respect to the module.

SAMPLE OUTPUT (file castle.out)

5
9
16
4 1 E

题解:无USACO输入输出,使用标准输入输出,题目可参见洛谷P1457

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
#include<iostream>
#include<utility>
using namespace std;
int m, n;
int arr[55][55];
bool visited[55][55];
pair<int,int> father[55][55];
int mapsize[55][55];
inline int _find(int x, int y) {
    return mapsize[father[x][y].first][father[x][y].second];
}
inline int getBit(int n, int pos) {
    return (n >> pos) & 1;
}
int dfs(int x, int y,int fatherx,int fathery) {
    if (x<1||x>n||y<1||y>m||visited[x][y])return 0;
    visited[x][y] = true;
    father[x][y] = pair<int, int>(fatherx, fathery);
    int tot = 0;
    if (!getBit(arr[x][y], 0))tot += dfs(x , y-1, fatherx, fathery);
    if (!getBit(arr[x][y], 1))tot += dfs(x-1, y, fatherx, fathery);
    if (!getBit(arr[x][y], 2))tot += dfs(x, y+1, fatherx, fathery);
    if (!getBit(arr[x][y], 3))tot += dfs(x+1, y, fatherx, fathery);
    return tot+1;
}
int main() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            father[i][j] = pair<int, int>(-1, -1);
        }
    }
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    int maxs = 0,room=0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int t = dfs(i, j, i, j);
            if (t != 0) {
                room++;
                mapsize[i][j] = t;
            }
            if (t > maxs)maxs = t;
        }
    }
    cout << room << endl << maxs << endl;
    int maxcombsquare = 0, wallx=-1, wally=-1;
    char pos;
    for (int j = m; j >=1; j--){
        for (int i = 1; i<=n ; i++) {
            if (j!=m&&getBit(arr[i][j], 2) && father[i][j] != father[i][j + 1]) {
                if (_find(i, j) + _find(i, j + 1) >= maxcombsquare) {
                    maxcombsquare = _find(i, j) + _find(i, j + 1);
                    wallx = i; wally = j; pos = 'E';
                }
            }
            if (i != 1 && getBit(arr[i][j], 1) && father[i][j] != father[i - 1][j]) {
                if (_find(i, j) + _find(i - 1, j) >= maxcombsquare) {
                    maxcombsquare = _find(i, j) + _find(i - 1, j);
                    wallx = i; wally = j; pos = 'N';
                }
            }
        }
    }
    cout << maxcombsquare << endl << wallx << " " << wally << " " << pos << endl;
}

洛谷 幻想迷宫

题号:1363
首先放上来一个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
#include<iostream>
#include<cstring>
using namespace std;
int n, m;
char map[1505][1505];
int visited[1505][1505][2];
bool dfs(int orix, int oriy){
    int x = (orix%n+n) % n, y = (oriy%m+m) % m;
    if (map[x][y] != 'S' && map[x][y] != '.')return false;
    if (orix== visited[x][y][0]&&oriy==visited[x][y][1])return false;
    if (visited[x][y][0] != -1)return true;
    visited[x][y][0] = orix;
    visited[x][y][1] = oriy;
    if (dfs(orix + 1, oriy))return true;
    if (dfs(orix - 1, oriy))return true;
    if (dfs(orix, oriy + 1))return true;
    if (dfs(orix, oriy - 1))return true;
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    while (cin >> n >> m){
        memset(visited, -1, sizeof(visited));
        for (int i = 0; i < n; i++)cin >> map[i];
        int sx, sy;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (map[i][j] == 'S'){
                    sx = i;
                    sy = j;
                    break;
                }
            }
        }
        bool flag = dfs(sx, sy);
        if (flag)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

题解页面:https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1363
该思路参考:作者: mike_he 更新时间: 2016-07-27 20:57
有两种思路是错误的,在下面列举一下:
继续阅读

洛谷 封锁阳光大学

题号:1330
这个属于搜索中的染色问题,之前不会,以后要多多学习。

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
#include<iostream>
#include<algorithm>
#include<list>
#include<queue>
using namespace std;
list<int> edge[100005];
int n, m;
int point[100005];
inline int color(int x){
    if (x == 1)return 2;
    else return 1;
}
int BFS(int i){
    int cnter1 = 0, cnter2 = 0;
    queue<pair<int, int>> q;
    q.push(pair<int, int>(i, 1));
    while (!q.empty()){
        pair<int, int> cur = q.front(); q.pop();
        if (point[cur.first] != 0){
            if (point[cur.first] != cur.second)return -1;
            continue;
        }
        point[cur.first] = cur.second;
        if (cur.second == 1)cnter1++;
        if (cur.second == 2)cnter2++;
        for (auto iter = edge[cur.first].begin(); iter != edge[cur.first].end(); iter++){
            q.push(pair<int, int>((*iter), color(cur.second)));
        }
    }
    return cnter1 < cnter2 ? cnter1 : cnter2;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    int sum = 0;
    for (int i = 1; i <= n; i++){
        if (point[i] == 0){
            int t=BFS(i);
            if (t == -1){
                cout << "Impossible";
                return 0;
            }
            else
                sum += t;
        }
    }
    cout << sum;
}

洛谷 八皇后

题号1219

感觉写的非常满意……哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
n=13都不用打表啦!

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n;
int cnt;//情况计数器
bool line[14],row[14],left_diagonal[26],right_diagonal[26];
//占用情况数组:行;列;左上-右下对角线;右上-左下对角线
int pos[14];
//记录每一行的棋子放在哪一列
inline int calculate_left_dia(int x,int y){//计算x行y列的棋子在第几个左上-右下对角线上
    return x+y-1;
}
inline int calculate_right_dia(int x,int y){//计算x行y列的棋子在第几个右上-左下对角线上
    return (n+1-x)+y-1;
}
void search(int level){//dfs搜索:行
    if(level==n+1){//递归基
        cnt++;
        if(cnt>3)return;
        for(int i=1;i<=n;i++){//输出结果
            cout<<pos[i]<<" ";
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++){//遍历列
        if(!line[i]&&!row[i]&&!left_diagonal[calculate_left_dia(level,i)]&&!right_diagonal[calculate_right_dia(level,i)]){//满足要求
            pos[level]=i;
            line[i]=true;row[i]=true;
            left_diagonal[calculate_left_dia(level,i)]=true;
            right_diagonal[calculate_right_dia(level,i)]=true;
            search(level+1);//继续深搜
            line[i]=false;row[i]=false;//回溯
            left_diagonal[calculate_left_dia(level,i)]=false;
            right_diagonal[calculate_right_dia(level,i)]=false;
        }
    }
}
int main(){
    cin>>n;
    search(1);
    cout<<cnt;
}

洛谷 滑雪(重要!)

题号:P1434
这道题需要留着细细品味……
这道题也挺恶心,用尽各种优化方法……
需要写一下注释,省得我以后看不懂自己写的代码……

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int array[105][105];
int memory[105][105];
bool check[105][105];
struct s{
    int x,y,n;
    bool operator < (s& s2){
        return this->n>s2.n;
    }
}ss[11025];
int r,c;
int shift_x[5]={0,-1,1,0,0},shift_y[5]={0,0,0,-1,1};//left,right,up,down
int safe_array(int x,int y){
    if(x>=1&&x<=r&&y>=1&&y<=c)return array[x][y];
    else return -1;
}//保证数组不越界
int dfs(int x,int y,int last){//dfs是从截止点step为0推到起始点的
    if(safe_array(x,y)==-1||last<=array[x][y]||check[x][y])return 0;
    if(memory[x][y]!=-1)return memory[x][y];
    check[x][y]=true;
    int max_=-1;
    for(int i=1;i<=4;i++){
        int t=dfs(x+shift_x[i],y+shift_y[i],array[x][y]);
        if(t>max_)max_=t;
    }
    check[x][y]=false;
    return memory[x][y]=max_+1;
}
int main(){
    memset(memory,-1,sizeof(memory));
    cin>>r>>c;
    int ptr=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>array[i][j];
            ss[ptr].x=i;
            ss[ptr].y=j;
            ss[ptr].n=array[i][j];
            ptr++;
        }
    }
    int max_=-1;
    sort(ss,ss+ptr);//先排序,由坡高到坡低去进行dfs,这样坡低的在刚一开始就会因为记忆化搜索直接return
    for(int i=0;i<ptr;i++){
        int t=dfs(ss[i].x,ss[i].y,ss[i].n+1);
        if(t>max_)max_=t;//收集最长路径
    }
    cout<<max_;
}