acwing::acwing845 命名空间参考

1. 八数码

更多...

类
struct	hash

函数
int	main (istream &cin, ostream &cout)
	TEST (acwing845, case1)
	TEST (acwing845, case2)

详细描述

1. 八数码

函数说明

main()

int acwing::acwing845::main	(	istream &	cin,
		ostream &	cout
	)

在文件 acwing.cpp 第 7097 行定义.

                                              {
            array<array<char, 3>, 3> target{};
            array<array<char, 3>, 3> grid{};
            unordered_set<array<array<char, 3>, 3>, hash> us;
            int start_x;
            int start_y;
            for(int i = 0; i < 9; i++) {
                cin >> grid[i / 3][i % 3];
                if(grid[i / 3][i % 3] == 'x') {
                    start_x = i / 3;
                    start_y = i % 3;
                }
                target[i / 3][i % 3] = i + '1';
            }
            target[2][2] = 'x';
            queue<tuple<array<array<char, 3>, 3>, int, int, int>> q;
            q.push(make_tuple(grid, 0, start_x, start_y));
            us.insert(grid);
            while(!q.empty()) {
                auto [g, step, x, y] = q.front();
                q.pop();
                if(g == target) {
                    cout << step;
                    return 0;
                }
                pair<int, int> nexts[4] = {
                        make_pair(x, y + 1),
                        make_pair(x, y - 1),
                        make_pair(x + 1, y),
                        make_pair(x - 1, y)};
                for(auto &[nx, ny]: nexts) {
                    if(nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                        swap(g[nx][ny], g[x][y]);
                        if(!us.contains(g)) {
                            us.insert(g);
                            q.push(make_tuple(g, step + 1, nx, ny));
                        }
                        swap(g[nx][ny], g[x][y]);
                    }
                }
            }
            cout << -1;
            return 0;
        }

被这些函数引用 TEST().

TEST() [1/2]

acwing::acwing845::TEST	(	acwing845	,
		case1
	)

在文件 acwing_test.cpp 第 3309 行定义.

                               {
            istringstream in("2  3  4  1  5  x  7  6  8");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("19", ans);
        }

引用了 main().

TEST() [2/2]

acwing::acwing845::TEST	(	acwing845	,
		case2
	)

在文件 acwing_test.cpp 第 3317 行定义.

                               {
            istringstream in("6 4 7 8 5 x 3 2 1");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("31", ans);
        }

引用了 main().