// 思路：3*3网格的状态看作一个节点，bfs层次遍历各节点，知道网格状态呈现正确排列；难点在于状态的表达（矩阵） 以及 如何记录每个状态的距离。

// 状态的表达：二维数组用字符串表示；如何记录状态是否被访问过了 --> 下标为字符串，自然想到哈希表，通过unordered_map::count()判断字符串对应状态是否访问过；
// 状态的转移：字符串与二维数组 下标与偏移 的计算技巧；BFS思想；

// unordered_map::count()是C++中的内置方法，用于通过给定 key 对unordered_map中存在的元素数量进行计数。
// 注意：由于unordered_map不允许存储具有重复键的元素，因此count()函数本质上检查unordered_map中是否存在具有给定键的元素。

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs(string start){
    string end = "12345678x";

    // 普通队列（非最小堆对应的优先级队列）
    queue<string> q;
    unordered_map<string, int> d;

    q.push(start);
    d[start] = 0;

    while (!q.empty()){
        auto t = q.front();
        q.pop();

        int distance = d[t];

        if (t == end)   return distance;

        // 状态转移
        int k = t.find('x');    // 下标从0开始；
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[k], t[3*a + b]);
                if (!d.count(t)){
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[3*a + b], t[k]);
            }
        }
    }
    return -1;
}

int main(){
    string start;

    for (int i = 0; i < 9; i ++){
        char c;
        cin >> c;
        start += c;
    }

    cout << dfs(start) << endl;

    return 0;
}

单点时限: 2.0 sec
内存限制: 256 MB
一天，sunny 不小心进入了一个迷宫，不仅很难寻找出路，而且有的地方还有怪物，但是 sunny 有足够的能力杀死怪物，但是需要一定的时间，但是 sunny 想早一点走出迷宫，所以请你帮助他计算出最少的时间走出迷宫，输出这个最少时间。

我们规定每走一格需要时间单位 1, 杀死怪物也需要时间 1, 如果不能走到出口，则输出 impossible. 每次走只能是上下左右 4 个方向。

输入格式
每次首先 2 个数 n,m (0<n,m≤200)，代表迷宫的高和宽，然后 n 行，每行 m 个字符。

S 代码你现在所在的位置。
T 代表迷宫的出口。

代表墙，你是不能走的。

X 代表怪物。
. 代表路，可以走。
处理到文件结束。

输出格式
输出最少的时间走出迷宫。不能走出输出 impossible。

样例
输入样例：

4 4
S.X.
#..#
..#.
X..T

4 4
S.X.
#..#
..#.
X.#T

输出样例：

6
impossible

代码

// 稠密图使用邻接矩阵，稀疏图使用邻接表；
// 相比权值相等的走迷宫，其各权值不同，本质上是最短路径问题，因此不可使用是否标记来判断是否更新；
// --> dis存储到该节点的最短路径 + 优先队列存储最短距离对应的顶点。
#include <iostream>
#include <stdio.h>
#include <queue>

using namespace std;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};     // 上右下左 顺时针四个方向的矩阵偏移

struct node {
    int x,  y, dis;
};

bool operator < (const node & a, const node & b) {
    return a.dis > b.dis;
}

const int N = 210;
char g[N][N];
int n, m;
typedef pair<int, int> PII;
struct node Prev[N][N];

void bfs(PII S, PII T){
    int sx = S.first, sy = S.second, tx = T.first, ty = T.second;

    priority_queue <node> heap;   // 小项堆
    heap.push({sx, sy, 0});
    g[sx][sy] = '#';

    while (!heap.empty())
    {
        node p = heap.top();
        heap.pop();

        if (p.x == tx && p.y == ty){
            cout << p.dis << endl;
            int x = tx, y = ty, d = p.dis;
            while(x != sx || y != sy)
            {
                printf("(%d, %d, %d) <- ", x, y, d);
                node t = Prev[x][y];
                x = t.x, y = t.y, d = t.dis;
            }
            printf("(%d, %d, %d)", sx, sy, 0);
            return;
        }

        for (int i = 0; i < 4; i ++)
        {
            int x = p.x + dx[i], y = p.y + dy[i];
            if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] != '#'){
                struct node np {x, y, 0};
                if (g[x][y] == 'X')     np.dis = p.dis + 2;
                // 此时下一顶点为终点时，既不为'.'，也不为'X'，但距离仍需要加一操作；因此直接使用if-else语句
                else np.dis = p.dis + 1;    // 两种情况：g[x][y] = '.' && g[x][y]为终点
                g[x][y] = '#';
                Prev[x][y] = {p.x, p.y, p.dis};
                heap.push(np);
            }
        }
    }
    cout << "impossible" << endl;
}

int main(){
    cin >> n >> m;
    PII S, T;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++){
            cin >> g[i][j];
            if (g[i][j] == 'S')
                S = {i, j};
            if (g[i][j] == 'T')
                T = {i, j};
        }

    bfs(S, T);

    return 0;
}

// 10^10会直接爆掉（memory >> 64MB） -->  稀疏图
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 150010;
int h[N], e[N], ne[N], w[N], idx;   //邻接表存储图
int st[N];   //state 记录是否找到了源点到该节点的最短距离
int dist[N];    //dist 数组保存源点到其余各个节点的距离
int n, m;   //图的节点个数和边数

typedef pair<int, int> PII;

void init(){
    memset(h, -1, sizeof h);
}

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    priority_queue <PII, vector<PII>, greater<PII>> heap;   // 小项堆
    heap.push({dist[1], 1});      // 插入距离distance与顶点编号vertex

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int distance = t.first, ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (!st[j] && dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    init();
    cin >> n >> m;
    while (m--){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    int result = dijkstra();

    cout << result << endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;
int g[N][N], dist[N];
bool st[N];
int n, m;

void init(){
    memset(g, 0x3f, sizeof g);
}

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);   // 第一步肯定是初始化顶点1到任意顶点（除自身外）的最短距离为无穷大；

    dist[1] = 0;

    for (int i = 0; i < n; i ++)
    {
        int t = -1;

        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t==-1 || dist[t]>dist[j]))
                t = j;

        st[t] = true;

        for (int j = 1; j <= n; j ++)
            if (!st[j])
                dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    init();
    cin >> n >> m;
    // 处理重边，选择最小的边作为邻接矩阵元素的值；关于自环无需处理，不会更新 / 已被标记；
    while (m--){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }

    int result = dijkstra();
    cout << result;

    return 0;
}

// dfs不用于寻找最短路径；bfs用于边权值相等的图求最短路径；权值不同的图使用最短路径算法，但复杂度较高；
// dp属于特殊的最短路问题(且为dfs思想)，相比最短路算法复杂度低一些。
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int g[N][N], d[N][N];   // d数组中-1记录未走过，值记录点到(1,1)的距离；
typedef pair<int, int> PII;
PII q[N * N];
int n, m;

void init(){
    memset(d, -1, sizeof d);
}

int bfs(){
    d[1][1] = 0;
    q[0] = {1, 1};

    int hh = 0, tt = 0;     // 队列的首指针head以及尾指针tail；

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};     // 上右下左 顺时针四个方向的矩阵偏移

    while (hh <= tt){
        PII t = q[hh ++];   // 队列中取一个元素；

        for (int i = 0; i < 4; i ++){
            int x = t.first + dx[i], y = t.second + dy[i];
            if ( x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == 0 && d[x][y] == -1 ){
                d[x][y] = d[t.first][t.second] + 1;
                q[++ tt] = {x, y};
            }
        }
    }

    return d[n][m];
}

int main(){
    init();
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}

#include <iostream>

using namespace std;

const int N = 10;
int n, k;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u){    // u代表第几行
    // k ++;
    // cout << k << endl;   // 剪枝之后节点的个数可能比n!还小；即时间复杂度与初始化的变量值有关。
    if (u == n)
    {
        for (int i = 0; i < n; i ++)
            puts(g[i]);
        puts("");
    }
    for (int i = 0; i < n; i ++)    // 此时i代表第几列
        if (!col[i] && !dg[u + i] && !udg[n - i + u])
        {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - i + u] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - i + u] = false;
            g[u][i] = '.';
        }
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            g[i][j] = '.';

    dfs(0);

    return 0;
}

#include <iostream>

using namespace std;

const int N = 10;
int n, k;
int path[N];
int state[N];

int dfs(int u){
    // k ++;
    // cout << "k = " << k << endl; // 时间复杂度是O( 1 + n*(n-1) + n*(n-1)*(n-2) + ... + n! )；总的全排列个数是n! -- 叶子节点个数。
    if (u > n)
    {
        for (int i = 1; i <= n; i ++)
            cout << path[i] << " ";
        cout << endl;
    }
    else 
    {
        for (int i = 1; i <= n; i ++)
        {
            if (!state[i])
            {
                state[i] = true;
                path[u] = i;
                dfs(u + 1);
                state[i] = false;
            }
        }
    }
}

int main(){
    cin >> n;

    dfs(1);

    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 200010;
int h[N], e[M], ne[M], idx;
int color[N];   // 0代表未染色，存在1、2两种不同的颜色；

void init(){
    memset(h, -1, sizeof h);
}

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int a, int c){
    color[a] = c;
    for (int i = h[a]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!color[j]){
            if (!dfs(j, 3 - c)) return false;
        }   // bug：if不打嵌套号直接匹配最近的else；
        else if (color[j] == c) return false;
    }
    return true;
}

int main(){
    init();
    int n, m;
    cin >> n >> m;
    while (m--){
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);  // 无向图，加两条有向边。
    }

    bool flag = true;
    for (int i = 1; i <= n; i ++)
        if (!color[i])
            if (!dfs(i, 1)){
                flag = false;
                break;
            }

    if (flag) puts("Yes");
    else puts("No");
    return 0;
}

#include<iostream>
#include<cstring>

using namespace std;

const int N = 510, M = 100010;
int h[N], e[M], ne[M], idx;
int n1, n2, m;

int match[N];
bool st[N];
bool noask[N];

void init(){
    memset(h, -1, sizeof h);
}

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int find(int a){
    for (int i = h[a]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j] && !noask[j])
        {
            st[j] = true;
            if (!match[j] || find(match[j]))
            {
                match[j] = a;
                return true;
            }
            else noask[j] = true; // //女生j无调整空间，以后不需要再询问该女生。
        }
    }
    return false;
}

int main(){
    init();
    cin >> n1 >> n2 >> m;
    while (m--){
        int a, b;
        cin >> a >> b;
        add(a,b);
    }

    int res = 0;
    memset(noask, false, sizeof noask);
    for (int i = 1; i <= n1; i ++){
        memset(st, false, sizeof st);
        if (find(i)) res ++;
    }

    cout << res << endl;
}

/*

1）一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，
石柱L面积只容得下一只青蛙落脚，同样右岸也有一石柱R，石柱R面积也只容得下一只青蛙落脚。
2）有一队青蛙从小到大编号：1，2，…，n。
3）初始时：青蛙只能趴在左岸的石头 L 上，按编号一个落一个，小的落在大的上面-----不允许大的在小的上面。 
4）在小溪中有S个石柱、有y片荷叶。 
5）规定：溪中的每个石柱上如果有多只青蛙也是大在下、小在上，每个荷叶只允许一只青蛙落脚。 
6）对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下。 
7）当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，
或从溪中荷叶、溪中石柱跳至右岸R上的青蛙也不允许再离开。 

问题：在已知小溪中有 s 根石柱和 y 片荷叶的情况下，最多能跳过多少只青蛙？

思路：经典找规律题目（首先，先简化题目条件，由简单情况到复杂情况再到一般情况；
其次，列数据，始终坚定一个原则：规律存在变化的数据中，即变中存在不变）

1. 不妨先假设柱子数为0，随着荷叶数由1到y可寻找出其规律：y + 1;
2. 这时再假设荷叶数为1，让柱子数不断从0开始持续增加1，可得到一个结果：2、4、8、16...2 ^ n;
3. 其原因是为什么呢？设定一个函数int Jump(int s , int y) (以L（左岸）、S1（柱子1）、
Y（荷叶）、S2（柱子2）、R（右岸）整个系统作为一个例子进行分析： 可以将（L、S1、Y、 S2、R ）系统划分为
（L、S1、Y、S2)系统与（S2、S1、Y、R）系统，即先把S2看作右岸，以（L、S1、Y、R(实际上为S2））为一个系统，
可过青蛙数为Jump(s - 1, 1) ；然后再把（L、S1、Y、 R）看为一个系统，可过青蛙同样也为Jump(s - 1, 1)； 这时你又需要把S2上的青蛙转到R上，于是可以以（S2、S1、Y、R）看为一个系统，于是Jump(s - 1, 1) 个青蛙也就过去到 右岸了。于是可得到一个规律：递归方程--jump(s, 1) = jump(s - 1, 1); 这时你把荷叶数一般化，举几个例子试验一下，可归纳出一个等式jump(s, y) = jump(s - 1, y)。
4. 最后，细心一点，将递归终止条件处理好，便AC了！           Nice！

*/

#include <iostream>

int Jump(int s, int y){
    int num = 0;
    if (s == 0)
        num = (y + 1);
    else if (y == 0)
        num = 2 * Jump(s - 1, 0);
         else
        num = 2 * Jump(s - 1, y);

    return num;
}

using namespace std;

int main()
{
    int s, y;
    cin >> s >> y;
    cout << Jump (s, y) << endl;

    return 0;
}