【kuangbin带你飞】专题一 【简单搜索】【--完结--】

发表于 | 更新于 | 分类于

比赛链接：点击打开链接

A - 棋盘问题

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int n, k, ans;
int che[10][10];
int vis[10];
void dfs(int row, int num)
{
    if(num == k)        //搜索到最后一个格子
    {
        ans++;
        return ;
    }
    if(row > n) return ;//越界
    for(int j = 1; j <= n; ++j)
        if(che[row][j] && !vis[j])
        {
            vis[j] = 1;
            dfs(row+1, num+1);
            vis[j] = 0;//搜索完成后归零
        }
    dfs(row+1, num);
    return ;
}

int main()
{
    char ch;
    while(~scanf("%d%d",&n,&k))
    {
        if(n == -1 && k == -1) break;
        ans = 0;
        memset(che, 0, sizeof(che));
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; ++i)
        {
            getchar();
            for(int j = 1; j <= n; ++j)
            {
                scanf("%c",&ch);
                if(ch == '#') che[i][j] = 1;
            }
        }
        dfs(1, 0); //第一行，符合条件的棋子数为0
        cout << ans << endl;
    }
    return 0;
}

B - Dungeon Master

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n, m, k, flag;
int startx, starty, startz;
int endx, endy, endz;
char e[35][35][35];
int nexta[6][3] = {{0,1,0},{0,-1,0},{1,0,0},{-1,0,0},{0,0,1},{0,0,-1} };
struct node
{
    int x, y, z;
    int sum;
};
int bfs(int a, int b, int c)
{
    node t1, t2, t3;
    queue<node> q;
    t1.x = a;
    t1.y = b;
    t1.z = c;
    t1.sum = 0;
    q.push(t1);
    while(!q.empty())
    {
        t2 = q.front();
        q.pop();
        for(int i = 0; i < 6; ++i)
        {
            t3.x = t2.x + nexta[i][0];
            t3.y = t2.y + nexta[i][1];
            t3.z = t2.z + nexta[i][2];
            t3.sum = t2.sum + 1;
            if(t3.x < 0 || t3.x >= n || t3.y < 0 || t3.y >= m || t3.z < 0 || t3.z >= k)//越界
                continue;
            if(e[t3.x][t3.y][t3.z] != '#')
            {
                if(t3.x == endx && t3.y == endy && t3.z == endz)
                {
                    flag = 1;
                    return t3.sum;
                }
                q.push(t3);
                e[t3.x][t3.y][t3.z] = '#';
            }
        }
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&k))
    {
        if(n == 0 && m == 0 && k == 0) break;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                for(int r = 0; r < k; ++r)
                {
                    cin >> e[i][j][r];
                    if(e[i][j][r] == 'S')
                    {
                        startx = i;
                        starty = j;
                        startz = r;
                    }
                    if(e[i][j][r] == 'E')
                    {
                        endx = i;
                        endy = j;
                        endz = r;
                    }
                }
        flag = 0;
        int sum = bfs(startx, starty, startz);
        if(flag == 1)
            cout << "Escaped in " << sum << " minute(s)." << endl;
        else
            cout << "Trapped!" << endl;
    }
    return 0;
}

C - Catch That Cow

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
67
68
69
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
int n, k, ans;
int vis[200005];

struct pos
{
    int x, t;
};
queue<pos> s;

void bfs(int x)
{
    pos b;
    b.x = x;
    b.t = 0;
    vis[x] = 1;
    s.push(b);
    while(!s.empty())
    {
        pos tem = s.front();
        s.pop();
        if(tem.x == k)
        {
            ans = tem.t;
            return ;
        }
        pos nex;     //开始向目标方向搜索
        nex.x = tem.x + 1;
        if(nex.x >= 0 && nex.x <= 100000 && vis[nex.x] == 0)
        {
            nex.t = tem.t + 1;
            vis[nex.x] = 1;
            s.push(nex);
        }
        nex.x = tem.x - 1;
        if(nex.x >= 0 && nex.x <= 100000 && vis[nex.x] == 0)
        {
            nex.t = tem.t + 1;
            vis[nex.x] = 1;
            s.push(nex);
        }
        nex.x = tem.x * 2;
        if(nex.x >= 0 && nex.x <= 100000 && vis[nex.x] == 0)
        {
            nex.t = tem.t + 1;
            vis[nex.x] = 1;
            s.push(nex);
        }
    }
}

int main()
{
    while(~scanf("%d%d",&n, &k))
    {
        memset(vis, 0, sizeof(vis));
        while(!s.empty()) s.pop();

        bfs(n);
        cout << ans << endl;
    }
    return 0;
}

D - Fliptile

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 16;
const int inf = 0x3f3f3f3f;
int m, n;
int cow[maxn][maxn];
int flip[maxn][maxn];
int opt[maxn][maxn];
int dir[][2] = {0, 0, 0, 1, 0, -1, -1, 0};

void getmap()
{
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j)
            scanf("%d",&cow[i][j]);
}

int getcolo(int x, int y)
{
    int tem = cow[x][y], xx, yy;
    for(int i = 0; i < 4; ++i)
    {
        xx = x + dir[i][0];
        yy = y + dir[i][1];
        if(xx >= 0 && xx < m && yy >= 0 && yy < n)
            tem += flip[xx][yy];
    }
    return tem & 1;
}

int dfs(int k)
{
    int sum, i, j;
    if(k == m -1)
    {
        for(i = 0; i < n; ++i)
            if(getcolo(k, i)) break;
        if(i != n) return -1;
        for(i = sum = 0; i < m; ++i)
            for(j = 0; j < n; ++j)
                if(flip[i][j]) sum++;
        return sum;
    }
    for(int j = 0; j < n; ++j)
        if(getcolo(k, j)) flip[k + 1][j] = 1;
    return dfs(k + 1);
}

void solve()
{
    int i, j, maxcase = 1 << n, ret = inf, num, tem;
    for(i = 0; i < maxcase; ++i)
    {
        memset(flip, 0, sizeof(flip));
        for(j = n - 1, tem = i; j >= 0; --j, tem >>= 1)
            flip[0][j] = tem & 1;
        num = dfs(0);
        if(num != -1 && num < ret)
        {
            ret = num;
            memcpy(opt, flip, sizeof(flip));
        }
    }

    if(ret == inf) cout << "IMPOSSIBLE" << endl;
    else
    {
        for(i = 0; i < m; ++i)
            for(j = 0; j < n; ++j)
                if(j == n -1) cout << opt[i][j] << endl;
                else cout << opt[i][j] << " ";
    }
}
int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        getmap();
        solve();
    }
    return 0;
}

E - Find The Multiple

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
int flag;
void dfs(unsigned long long t, int n, int k)
{
    if(flag) return ; //已发现答案 退出
    if(t % n == 0)
    {                 //输出答案并标记
        cout << t << endl;
        flag = 1;
        return ;
    }
    if(k == 19) return ;  //到第19层，回溯
    dfs(t*10, n, k+1);    //搜索t*10
    dfs(t*10+1, n, k+1);  //搜索t*10+1
}
int main()
{
    int n;
    while(~scanf("%d",&n) && n)
    {
        flag = 0;
        dfs(1, n, 0);
    }
    return 0;
}

F - Prime Path

AC代码：

//要选G++，C++会CE（我也不知道为什么

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int Max = 10010;
int m, n;
struct node
{
    int x;
    int sum;
};
int pri[Max];
int vis[Max];
int bfs()
{
    memset(vis, 0, sizeof(vis));
    node now, nex;
    now.x = n;
    now.sum = 0;
    queue<node> q;
    vis[n] = 1;
    q.push(now);
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        if(now.x == m)  return now.sum;
        for(int i = 0; i < 10; ++i)   //换个位
        {
            nex.x = now.x/10*10+i;
            nex.sum = now.sum + 1;
            if(!vis[nex.x] && !pri[nex.x])//未访问过此数并且这是个素数
            {
                vis[nex.x] = 1;
                q.push(nex);
            }
        }
        for(int i = 0; i < 10; ++i)  //换十位
        {
            int tem = now.x % 10;
            nex.x = now.x/100*100+(10*i)+tem;
            nex.sum = now.sum + 1;
            if(!vis[nex.x] && !pri[nex.x])
            {
                vis[nex.x] = 1;
                q.push(nex);
            }
        }
        for(int i = 0; i < 10; ++i)   //换百位
        {
            int tem = now.x % 100;
            nex.x = now.x/1000*1000+(100*i)+tem;
            nex.sum = now.sum + 1;
            if(!vis[nex.x] && !pri[nex.x])
            {
                vis[nex.x] = 1;
                q.push(nex);
            }
        }
        for(int i = 1; i < 10; ++i)  //换千位,要从1开始哦
        {
            nex.x = now.x%1000 + i*1000;
            nex.sum = now.sum + 1;
            if(!vis[nex.x] && !pri[nex.x])
            {
                vis[nex.x] = 1;
                q.push(nex);
            }
        }
    }
    return 0;
}
int main()
{
    int t;
    memset(pri, 0, sizeof(pri));
    pri[1] = 1;
    pri[0] = 1;
    m=sqrt(Max)+1;
    for(int i = 2; i < m; i++)
    {
        if(!pri[i])
        {
            for(int j=i*i;j<=Max;j+=i)
            {
                pri[j]=1;
            }
        }
    }
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d%d",&m,&n);
            printf("%d\n",bfs());
        }
    }
    return 0;
}

G - Shuffle’m Up

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
string s1, s2, s, ans;
int main()
{
    int t, flag, num, n;
    while(~scanf("%d",&t))
    {
        for(int cou = 1; cou <= t; ++cou)
        {
            num = 0;
            map<string, int> tem;
            scanf("%d",&n);
            int j = 0;
            cin >> s1 >> s2 >> ans;
            while(1)
            {
                num++;
                s.clear();
                for(int i = 0; i < n; ++i)
                {
                    s += s2[i];
                    s += s1[i];
                }
                if(s == ans)
                {
                    flag = 1;
                    break;
                }
                else
                {
                    if(tem[s])
                    {
                        flag = 0;
                        break;
                    }
                    tem[s] = 1;
                }
                s1 = s2 = "";
                for(int i = 0; i < n; ++i)
                    s1 += s[i];
                for(int i = n; i < 2*n; ++i)
                    s2 += s[i];
            }
            if(flag)
                cout << cou << " " << num << endl;
            else
                cout << cou << " -1" << endl;
        }
    }
    return 0;
}

H - Pots

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
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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const int inf = 0x3f3f3f3f;
int a, b, c;
int flag, res;
int vis[105][105];
char pa[10010], pp[10010];
void dfs(int x, int y, int dep)
{
    if(dep > res) return ;
    if(x == c || y == c)  //找到目标
    {
        if(dep < res)
        {
            flag = 1;
            res = dep;
            for(int i = 0; i < res; ++i)
                pa[i] = pp[i];
        }
        return ;
    }
    if(x < a && !vis[a][y])//FILL 1
	{
		vis[a][y] = 1;
		pp[dep] = 'f';
		dfs(a, y, dep+1);
		vis[a][y] = 0;
	}
	if(y < b && !vis[x][b])//FILL 2
	{
		vis[x][b] = 1;
		pp[dep] = 'F';
		dfs(x, b, dep+1);
		vis[x][b] = 0;
	}
	if(x > 0 && !vis[0][y])//DROP 1
	{
		vis[0][y] = 1;
		pp[dep] = 'd';
		dfs(0, y, dep+1);
		vis[0][y] = 0;
	}
	if(y > 0 && !vis[x][0])//DROP 2
	{
		vis[x][0] = 1;
		pp[dep] = 'D';
		dfs(x, 0, dep+1);
		vis[x][0] = 0;
	}
	if(x > 0 && y < b)//POUR(1,2)
	{
		int t = min(x, b-y);
		if(!vis[x-t][y+t])
		{
			vis[x-t][y+t] = 1;
			pp[dep] = 'p';
			dfs(x-t, y+t, dep+1);
			vis[x-t][y+t] = 0;
		}
	}
	if(y > 0 && x < a)//POUR(2,1)
	{
		int t = min(y, a-x);
		if(!vis[x+t][y-t])
		{
			vis[x+t][y-t] = 1;
			pp[dep] = 'P';
			dfs(x+t, y-t, dep+1);
			vis[x+t][y-t] = 0;
		}
	}
	return ;
}
int main()
{
    while(~scanf("%d%d%d",&a,&b,&c) && (a||b||c))
    {
        memset(vis, 0, sizeof(vis));
        vis[0][0] = 1;
        flag = 0;
        res = inf;
        dfs(0, 0, 0);
        if(flag)
        {
            cout << res << endl;
            for(int i = 0; i < res; ++i)
            {
                if(pa[i] == 'f')
                    cout << "FILL(1)" << endl;
                else if(pa[i] == 'F')
                    cout << "FILL(2)" << endl;
                else if(pa[i] == 'd')
                    cout << "DROP(1)" << endl;
                else if(pa[i] == 'D')
                    cout << "DROP(2)" << endl;
                else if(pa[i] == 'p')
                    cout << "POUR(1,2)" << endl;
                else if(pa[i] == 'P')
                    cout << "POUR(2,1)" << endl;
            }
        }
        else cout << "impossible" << endl;
    }
    return 0;
}

I - Fire Game

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
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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, tmin, tmax;
int mapa[15][15], vis[15][15];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0} };
int visit[15][15][15][15];
struct state
{
    int x, y;
    int t;
};
void bfs(int x1, int y1, int x2,int y2)
{

    queue<state> s;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            vis[i][j] = mapa[i][j];

    state p;
    p.x = x1; p.y = y1; p.t = 0; s.push(p);
    p.x = x2; p.y = y2; p.t = 0; s.push(p);
    vis[x1][y1] = vis[x2][y2] = 0;

    while(!s.empty())
    {
        state q;
        q = s.front();
        s.pop();
        tmax = q.t;
        for(int i = 0; i < 4; ++i)
        {
            state tem;
            tem.x = q.x + dir[i][0];
            tem.y = q.y + dir[i][1];
            tem.t = q.t + 1;
            if(tem.x < 1 || tem.x > n || tem.y < 1 || tem.y > m) continue;
            if(!vis[tem.x][tem.y]) continue;
            vis[tem.x][tem.y] = 0;
            s.push(tem);

        }
    }

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(vis[i][j]) tmax = inf;
}
int main()
{
    int t, cou;
    char c;
    while(~scanf("%d",&t))
    {
        for(cou = 1; cou <= t; ++cou)
        {
            scanf("%d%d",&n, &m);
            getchar();
            for(int i = 1; i <= n; ++i)
            {
                for(int j = 1; j <= m; ++j)
                {
                    cin >> c;
                    if(c == '#')  mapa[i][j] = 1;
                    else mapa[i][j] = 0;
                }
            }
            tmin = inf;
            memset(visit, 0, sizeof(visit));
            for(int i = 1; i <= n; ++i)
                for(int j = 1; j <= m; ++j)
                    for(int p = 1; p <= n; ++p)
                        for(int q = 1; q <= m; ++q)
                        {
                            if(mapa[i][j] && mapa[p][q] && !visit[i][j][p][q])
                            {
                                visit[i][j][p][q] = 1;
                                bfs(i, j, p, q);
                                tmin = min(tmin, tmax);
                            }
                        }
            if(tmin == inf)
                printf("Case %d: -1\n",cou);
            else
                printf("Case %d: %d\n",cou, tmin);
        }
    }
    return 0;
}

J - Fire!

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
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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n, m;
char mapa[1005][1005];
int fir[1005][1005];
int vis[1005][1005];
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1} };
struct node
{
    int x, y;
};
queue<node> q1;
queue<node> q2;

void Fbfs()
{
    node now;
    while(!q1.empty())
    {
        now = q1.front();
        q1.pop();
        for(int i = 0; i < 4; ++i)
        {
            int xx = now.x + dir[i][0];
            int yy = now.y + dir[i][1];
            if(xx > n || xx < 1 || yy < 1 || yy > m) continue;
            if(mapa[xx][yy] == '#' || mapa[xx][yy] == 'F') continue;
            if(fir[xx][yy] != -1) continue;
            node tem;
            fir[xx][yy] = fir[now.x][now.y] + 1;
            tem.x = xx;
            tem.y = yy;
            q1.push(tem);
        }
    }
}

void Jbfs()
{
    node now;
    while(!q2.empty())
    {
        now = q2.front();
        q2.pop();
        if(now.x == 1 || now.x == n || now.y == 1 || now.y == m)
        {
            cout << vis[now.x][now.y]+1 << endl;
            return ;
        }
        for(int i = 0; i < 4; ++i)
        {
            int xx = now.x + dir[i][0];
            int yy = now.y + dir[i][1];
            if(xx > n || xx < 1 || yy < 1 || yy > m) continue;
            if(mapa[xx][yy] == '#' || mapa[xx][yy] == 'F' || mapa[xx][yy] == 'J') continue;
            if(vis[xx][yy] != -1) continue;
            if(fir[xx][yy] == -1 || (vis[now.x][now.y] < fir[xx][yy] - 1))
            {
                node tem;
                vis[xx][yy] = vis[now.x][now.y] + 1;
                tem.x = xx;
                tem.y = yy;
                q2.push(tem);
            }
        }
    }
    cout << "IMPOSSIBLE" << endl;
}
int main()
{
    int t;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d%d",&n,&m);
            node peop, fire;
            memset(vis, -1, sizeof(vis));
            memset(fir, -1, sizeof(fir));
            while(!q1.empty())  q1.pop();
            while(!q2.empty())  q2.pop();
            for(int i = 1; i <= n; ++i)
                for(int j = 1; j <= m; ++j)
                {
                    cin >> mapa[i][j];
                    if(mapa[i][j] == 'F')
                    {
                        fire.x = i;
                        fire.y = j;
                        q1.push(fire);
                        fir[i][j] = 0;
                    }
                    if(mapa[i][j] == 'J')
                    {
                        peop.x = i;
                        peop.y = j;
                        q2.push(peop);
                        vis[i][j] = 0;
                    }
                }
            Fbfs();
            Jbfs();
        }
    }
    return 0;
}

K - 迷宫问题

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[5][5];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1} };
struct node
{
    int x, y, pre;
}q[100];
int fir = 0,las = 1;

void print(int n)
{
    if(q[n].pre != -1)
    {
        print(q[n].pre);
        printf("(%d, %d)\n",q[n].x, q[n].y);
    }
}

void bfs(int x, int y)
{
    q[fir].pre = -1;
    q[fir].x = x;
    q[fir].y = y;
    int xx, yy;
    while(fir < las)
    {
        for(int i = 0; i < 4; ++i)
        {
            xx = q[fir].x + dir[i][0];
            yy = q[fir].y + dir[i][1];
            if(xx < 0 || yy < 0 || xx >= 5 || yy >= 5 || a[xx][yy]) continue;

            a[xx][yy] = 1;
            q[las].pre = fir;
            q[las].x = xx;
            q[las].y = yy;
            las++;

            if(xx == 4 && yy == 4) print(fir);
        }
        fir++;
    }
}
int main()
{
    for(int i = 0; i < 5; ++i)
        for(int j = 0; j < 5; ++j)
        cin >> a[i][j];
    printf("(0, 0)\n");
    bfs(0, 0);
    printf("(4, 4)\n");
    return 0;
}

L - Oil Deposits

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 105;
char pic[maxn][maxn];
int m, n, idx[maxn][maxn];

void dfs(int r, int c, int id)
{
    if(r < 0 || r >= m || c < 0 || c >= n) return ;//越界
    if(idx[r][c] > 0 || pic[r][c] != '@') return ;//非'@'格子或已访问过格子
    idx[r][c] = id;
    for(int dr = -1; dr <= 1; ++dr)
        for(int dc = -1; dc <= 1; ++dc)
        if(dr != 0 || dc != 0) dfs(r+dr, c+dc, id);
}

int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        if(n == 0 && m == 0) break;
        for(int i = 0; i < m; ++i) scanf("%s",pic[i]);
        memset(idx, 0, sizeof(idx));
        int cnt = 0;
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
            if(idx[i][j] == 0 && pic[i][j] == '@') dfs(i, j, ++cnt);
            cout << cnt << endl;
    }
    return 0;
}

M - 非常可乐

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
int rq[3]; //容器的容量
int vis[105][105][105];
struct qingkuang
{
    int num[3];
    int out;
} now, nex;

void bfs(int ss, int n, int m)
{
    memset(vis, 0, sizeof(vis));
    queue<qingkuang> s;
    now.num[0] = ss;
    now.num[1] = n;
    now.num[2] = m;
    vis[ss][n][m] = 1;
    now.out = 0;
    s.push(now);
    while(!s.empty())
    {
        now = s.front();
        s.pop();
        for(int i = 0; i < 2; ++i)   //是否满足情况(共三种，这里有种判断了2次，还可以优化一下)
            for(int j = 0; j < 3; ++j)
            {
                if(i == j) continue;
                if(now.num[i] == now.num[j] && now.num[3-i-j] == 0)
                {
                    cout << now.out << endl;
                    return ;
                }
            }

//所有倒的方法一共就6种，分别为1->2,1->3,2->1,2->3,3->1,3->2
//开始模拟倒可乐的过程
        for(int i = 0; i < 3; ++i)
        {
            for(int j = 0; j < 3; ++j)
            {
                if(i == j) continue;
                if(now.num[i] + now.num[j] <= rq[j])   //i全部倒入j中
                {
                    nex.num[j] = now.num[j] + now.num[i];
                    nex.num[i] = 0;
                }
                else          //j被倒满
                {
                    nex.num[i] = now.num[i] - (rq[j] - now.num[j]);
                    nex.num[j] = rq[j];
                }
                for(int k = 0; k < 3; ++k)  //维护一下当前步骤
                {
                    if(k == i || k == j) continue;
                    nex.num[k] = now.num[k];
                }
                nex.out = now.out + 1;
                if(vis[nex.num[0]][nex.num[1]][nex.num[2]] == 0)
                {
                    vis[nex.num[0]][nex.num[1]][nex.num[2]] = 1;
                    s.push(nex);
                }
            }
        }
    }
    cout << "NO" << endl;
    return ;
}

int main()
{
    int s, n, m;
    while(~scanf("%d%d%d",&s, &n, &m) && (s || n || m))
    {
        rq[0] = s;
        rq[1] = n;
        rq[2] = m;
        bfs(s, 0, 0);
    }
    return 0;
}

N - Find a way

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
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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
char mapa[205][205];
int vis[205][205];
int dis[2][205][205];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1} };
int n, m;
int startx, starty;
int endx, endy;
struct node
{
    int x, y;
    int sum;
};

void bfs(int idx, int x, int y)
{
    memset(vis, 0, sizeof(vis));
    vis[x][y] = 1;
    queue<node> q;
    node now, nex;
    now.x = x;
    now.y = y;
    now.sum = 0;
    q.push(now);
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        if(mapa[now.x][now.y] == '@')
            dis[idx][now.x][now.y] = now.sum;
        for(int i = 0; i < 4; ++i)
        {
            nex.x = now.x + dir[i][0];
            nex.y = now.y + dir[i][1];
            if(nex.x < 0 || nex.x >= n || nex.y < 0 || nex.y >= m)  continue; //越界
            if(vis[nex.x][nex.y])  continue;
            if(mapa[nex.x][nex.y] == '#') continue;
            vis[nex.x][nex.y] = 1;
            nex.sum = now.sum + 1;
            q.push(nex);
        }
    }
}

int main()
{

    while(~scanf("%d%d",&n,&m))
    {
        memset(mapa, 0, sizeof(mapa));
        memset(dis, inf, sizeof(dis));   //初始化为无穷远
        for(int i = 0; i < n; ++i)
            scanf("%s",mapa[i]);

        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(mapa[i][j] == 'Y')
                {
                    startx = i;
                    starty = j;
                }
                if(mapa[i][j] == 'M')
                {
                    endx = i;
                    endy = j;
                }
            }

        bfs(0, startx, starty);
        bfs(1, endx, endy);
        int ans = inf;

        /*cout << 233 << endl;
        cout << startx << " " << starty << endl;
        cout << endx << " " << endy << endl;*/

        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(mapa[i][j] == '@')
                    ans = min(ans, dis[0][i][j] + dis[1][i][j]);

        cout << ans*11 << endl;
    }
    return 0;
}

点击并拖拽以移动

Donate comment here
0%