@sensitive-cs 2017-03-11T03:11:11.000000Z 字数 12302 阅读 1089

[kuangbin带我飞]专题一简单搜索

题解

poj1321 棋盘问题
题意：
给你一个棋盘，n*n，k个棋子，其中，棋子放置的时候不能在同一列或者同一排，问有多少种方案可以放置这k个棋子。
思路：
dfs，搜索与回溯，这题我做的时候忽略了一个地方，就是一行不放棋子都可以的，并不是每一行都要放棋子，以后要注意类似的问题。
代码（看注释的地方：

#include <stdio.h>
#include <string.h>
char mp[10][10];
int mmp[10][10];
int ans = 0;
int n,k;
bool judge(int x,int y)
{
    for (int i = 0;i < n;i++)
        if (mmp[i][y] == 1)
            return true;
    return false;
}
void dfs(int l,int num)
{
    if (num == k)
    {
        ans++;
        return;
    }
    if (l >= n) return;
    for (int i = 0;i < n;i++)
    {
        if(mp[l][i] == '#')
        {
            if (!judge(l,i))
            {
                mmp[l][i] = 1;
                dfs(l+1,num+1);
                mmp[l][i] = 0;
            }
        }
    }
    dfs(l+1,num);//不放棋子也可以，注意！！！
    return;
}
int main()
{
    while (scanf("%d%d",&n,&k) != EOF)
    {
        memset(mp,0,sizeof(mp));
        memset(mmp,0,sizeof(mmp));
        if (n == -1 && k == -1) break;
        for (int i = 0;i < n;i++)
            scanf(" %s",mp[i]);
        ans = 0;
        if (k == 1)
        {
            for (int i = 0;i < n;i++)
                for (int j = 0;j < n;j++)
                if (mp[i][j] == '#') ans++;
        }
        else
            dfs(0,0);
        printf("%d\n",ans);
    }
    return 0;
}

poj2251 degon master
题意：
给出一个三维的迷宫，人可以走空房子，问有无可能走出，如果有，输出最短时间。
思路：
广度优先搜索，无fuck可说。
注意：
有很多地方未思考到。比如0 0 0的退出条件。还有就是判断可走的点时，忘记了坐标的限制，还有就是可行的点的判断应该是!#，我却直接写成了=='.'，太不应该了。仔细审题，在写程序之前最好思考一下如何减少bug。
代码：

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int inf = 1000000000;
char maze[35][35][35];
int dis[35][35][35];
int dx[6] = {0,1,0,-1,0,0};
int dy[6] = {1,0,-1,0,0,0};
int dz[6] = {0,0,0,0,1,-1};
struct cor
{
    int x,y,z;
};
typedef cor mp;
queue<mp> mmp;
int main()
{
    int l,r,c;
    while (scanf("%d%d%d",&l,&r,&c) != EOF)
    {
        if (l == 0 && r == 0 && c == 0) break;
        memset(maze,0,sizeof(maze));
        while (mmp.size()) mmp.pop();
        int si,sj,sk,ei,ej,ek;
        for (int i = 0;i < 35;i++)
            for (int j = 0;j < 35;j++)
            for (int k = 0;k < 35;k++)
            dis[i][j][k] = inf;
        for (int i = 0;i < l;i++)
            for (int j = 0;j < r;j++)
            scanf(" %s",maze[i][j]);
        for (int i = 0;i < l;i++)
            for (int j = 0;j < r;j++)
            for (int k = 0;k < c;k++)
            {
                if (maze[i][j][k] == 'S')
                {
                    si = i;sj = j;sk = k;
                }
                if (maze[i][j][k] == 'E')
                {
                    ei = i;ej = j;ek = k;
                }
            }
        dis[si][sj][sk] = 0;
        mp sta;
        sta.x = si;sta.y = sj;sta.z = sk;
        mmp.push(sta);
        while (mmp.size())
        {
            mp t = mmp.front();
            mmp.pop();
            int a = t.x,b = t.y,p = t.z;
            if (a == ei && b == ej && p == ek) break;
            for (int i = 0;i < 6;i++)
            {
                int a1 = a+dx[i],b1 = b+dy[i],c1 = p+dz[i];
                if (a1 >= l || a1 < 0 || b1 >= r || b1 < 0 || c1 >= c || c1 < 0) continue;
                if (dis[a1][b1][c1] == inf && maze[a1][b1][c1] != '#')
                {
                    dis[a1][b1][c1] = dis[a][b][p] + 1;
                    mp tt;
                    tt.x = a1,tt.y = b1,tt.z = c1;
                    mmp.push(tt);
                }
            }
        }
        if (dis[ei][ej][ek] == inf)
            printf("Trapped!\n");
        else
            printf("Escaped in %d minute(s).\n",dis[ei][ej][ek]);
    }
    return 0;
}

poj3278 catch tha cow
题意：
在一条坐标轴上，农夫在n点，羊在k点，羊不动，农夫每次花一分钟可以移动到n+1，n-1，2*n，问农夫到羊的位置，所花最短的时间。
思路：
宽搜。注意当vis[k] != inf,并且vis[t]+1 < vis[k]也是有可能的，因为走得路线可能重复。注意审题！！！！
代码：

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int vis[100005];
const int inf = 100000000;
int ti = 0;
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for (int i = 0;i < 100005;i++) vis[i] = inf;
    vis[n] = 0;
    queue<int> s;
    s.push(n);
    if (n == k) printf("0\n");
    else
    {
        while (s.size())
        {
            int t = s.front();
            s.pop();
            if (t == k) break;
            int x = t * 2,y = t-1,z = t+1;
            if (x >= 0 && x <= 100000&&vis[x] == inf  ) {vis[x] = vis[t] + 1;s.push(x);}
            else if (x >= 0 && x <= 100000 &&vis[x] != inf &&  vis[t]+1 < vis[x]) {vis[x] = vis[t]+1;s.push(x);}
            if (y >= 0 && y <= 100000 &&vis[y] == inf ) {vis[y] = vis[t] + 1;s.push(y);}
            else if (y >= 0 && y <= 100000 && vis[y] != inf &&  vis[t]+1 < vis[y]) {vis[y] = vis[t]+1;s.push(y);}
            if (z >= 0 && z <= 100000 && vis[z] == inf) {vis[z] = vis[t]+1;s.push(z);}
            else if (z >= 0 && z <= 100000 && vis[z] != inf &&  vis[t]+1 < vis[z]) {vis[z] = vis[t]+1;s.push(z);}
        }
        printf("%d\n",vis[k]);
    }
    return 0;
}

poj3984：迷宫问题
题意：
中文题。
思路：
宽搜。用类似于指针的方法，记录当前节点的每一个前节点，用到了map，因为除了开始节点的每一个节点，只可能有一个father。最后用栈将坐标倒一下。
代码：

#include <stdio.h>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
using namespace std;
typedef pair<int,int> p;
map<p,p> mmp;
queue<p> ro;
stack<p> out;
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
int mp[5][5];
bool vis[5][5];
int main()
{
    for (int i = 0;i < 5;i++)
        for (int j = 0;j < 5;j++)
        scanf("%d",&mp[i][j]);
    vis[0][0] = 1;
    ro.push(p(0,0));
    while (ro.size())
    {
        p t = ro.front();
        ro.pop();
        if (t.first == 4 && t.second == 4) break;
        for (int i = 0;i < 4;i++)
        {
            int x = t.first + dx[i],y = t.second + dy[i];
            if (x >= 0 && x < 5 && y >= 0 && y < 5 && !vis[x][y] && mp[x][y] == 0)
            {
                vis[x][y] = 1;
                mmp[p(x,y)] = p(t.first,t.second);
                ro.push(p(x,y));
            }
        }
    }
    int x = 4,y = 4;
    out.push(p(x,y));
    while (1)
    {
        int tx = x,ty = y;
        x = mmp[p(tx,ty)].first;
        y = mmp[p(tx,ty)].second;
        out.push(p(x,y));
        if (x == 0 && y == 0) break;
    }
    while (out.size())
    {
        p tc = out.top();
        out.pop();
        printf("(%d, %d)\n",tc.first,tc.second);
    }
    return 0;
}

hdu2612：find a way
题意：
有两人要在肯德基相遇，kfc有很多家，问两人到达同一家kfc所需的最少时间。
思路：
宽搜。开始是找出每一个肯德基，然后每一个肯德基进行宽搜，结果t了还是rt了。后来去看了题解，直接对两个人的家进行bfs就行了，开始没想到，后来就想通了，还是题做得太少啊。
代码：

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int n,m;
int dx[4] = {0,-1,1,0};
int dy[4] = {1,0,0,-1};
char mp[205][205];
int dist1[205][205];
int dist2[205][205];
typedef pair<int,int> p;
queue<p> mmp;
void bfs1(int sx,int sy)
{
    dist1[sx][sy] = 0;
    mmp.push(p(sx,sy));
    while (mmp.size())
    {
        p t = mmp.front();
        mmp.pop();
        int tx = t.first,ty = t.second;
        for (int i = 0;i < 4;i++)
        {
            int x = tx + dx[i],y = ty + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && dist1[x][y] == -1 && mp[x][y] != '#')
            {
                dist1[x][y] = dist1[tx][ty] + 11;
                mmp.push(p(x,y));
            }
        }
    }
}
void bfs2(int sx,int sy)
{
    dist2[sx][sy] = 0;
    mmp.push(p(sx,sy));
    while (mmp.size())
    {
        p t = mmp.front();
        mmp.pop();
        int tx = t.first,ty = t.second;
        for (int i = 0;i < 4;i++)
        {
            int x = tx + dx[i],y = ty + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && dist2[x][y] == -1 && mp[x][y] != '#')
            {
                dist2[x][y] = dist2[tx][ty] + 11;
                mmp.push(p(x,y));
            }
        }
    }
}
int main()
{
    while (scanf("%d%d",&n,&m) != EOF)
    {
        memset(mp,0,sizeof(mp));
        memset(dist1,-1,sizeof(dist1));
        memset(dist2,-1,sizeof(dist2));
        for (int i = 0;i < n;i++)
            scanf("%s",mp[i]);
        int yx,yy,mx,my;
        for (int i = 0;i < n;i++)
            for (int j = 0;j < m;j++)
        {
            if (mp[i][j] == 'Y')
            {
                yx = i;yy = j;
            }
            if (mp[i][j] == 'M')
            {
                mx = i;my = j;
            }
        }
        while (mmp.size()) mmp.pop();
        bfs1(yx,yy);
        while (mmp.size()) mmp.pop();
        bfs2(mx,my);
        int ans = 1000000000;
        for (int i = 0;i < n;i++)
            for (int j = 0;j < m;j++)
        {
            if (mp[i][j] == '@')
            {
                if (dist1[i][j] != -1 && dist2[i][j] != -1)
                {
                    int k = dist1[i][j] + dist2[i][j];
                    if (k < ans) ans = k;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdu1241 oil deposits
题意：
找出图中所有的八连块。
思路：
深搜，将所有的与@相连的全部变成*，包括自己，计算一共dfs了几次。
坑：输入用%c，不要用%s，不知道怎么就有问题了QAQ。
代码：

#include <stdio.h>
#include <string.h>
char mp[120][120];
int m,n;
int dx[8] = {0,1,0,-1,1,-1,1,-1};
int dy[8] = {1,0,-1,0,-1,1,1,-1};
void dfs(int x,int y)
{
    mp[x][y] = '*';
    for (int i = 0;i < 8;i++)
    {
        int tx = x + dx[i],ty = y + dy[i];
        if (tx >= 1 && tx <= m && ty >= 1 && ty <= n && mp[tx][ty] == '@')
            dfs(tx,ty);
    }
    return;
}
int main()
{
    while (scanf("%d%d",&m,&n) != EOF)
    {
        memset(mp,0,sizeof(mp));
        if (m == 0 && n == 0) break;
        for (int i = 1;i <= m;i++)
            for (int j = 1;j <= n;j++)
                scanf(" %c",&mp[i][j]);
        int ans = 0;
        for (int i = 1;i <= m;i++)
            for (int j = 1;j <= n;j++)
        {
            if (mp[i][j] == '@')
            {
                ans++;
                dfs(i,j);
            }
        }
        /*for (int i = 1;i <= m;i++)
            for (int j = 1;j <= n;j++)
            printf("%c\n",mp[i][j]);*/
        printf("%d\n",ans);
    }
    return 0;
}

poj1426 find the multiple
题意：
给出一个数，找出一个数，满足是这个数的倍数，且所有的数位要么是1，要么是0。
思路：
一开始以为要用数组构造，高精度进行计算，这就触及到我知识的盲区了。搜了一下题解，原来unsighed long long也可以存下。
所以后面一通乱搞，将最早得出的答案记录下来就返回。看代码。
代码：

#include <stdio.h>
#include <string.h>
int n;
int ans = 0;
unsigned long long res = 0;
void dfs(unsigned long long k,int num)
{
    if (num >= 19) return;
    if (k % n == 0)
    {
        res = k;
        ans = 1;
        return;
    }
    if (ans == 1) return;
    dfs(k*10,num+1);dfs(k*10 + 1,num+1);
}
int main()
{
    while (scanf("%d",&n) != EOF && n)
    {
        ans = 0;
        dfs(1,0);
        printf("%I64d\n",res);
    }
    return 0;
}

poj3126 prime path
题意：
找到一个质数改变为另一个质数所需的最小步数。改变的规则是变为另一个只有一位数字与原数字不同的质数。
思路：
首先利用埃氏筛筛出质数，然后宽搜，不过其中判断显得有点麻烦。
代码：

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int a[10005];
typedef pair<int,int> p;
p c[10005];
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int m,n;
        scanf("%d%d",&m,&n);
        memset(a,-1,sizeof(a));
        memset(c,0,sizeof(c));
        a[0] = a[1] = 0;
        for (int i = 2;i <= 10000;i++)
            if (a[i] == -1)
        {
            for (int j = 2*i;j <= 10000;j += i) a[j] = 0;
        }
        int sum = 0;
        for (int i = 1000;i < 10000;i++)
            if (a[i] == -1)
        {
            c[sum].first = i;
            c[sum].second = 0;
            sum++;
        }
        queue<p> mmp;
        mmp.push(p(m,0));
        a[m] = 0;
        while (mmp.size())
        {
            p tt = mmp.front();
            mmp.pop();
            if (tt.first == n) break;
            int key = tt.first;
            for (int i = 0;i < sum;i++)
            {
                int tx = c[i].first;
                if (a[tx] == 0) continue;
                int aa = key / 1000,bb = key % 1000 / 100,cc = key % 100 / 10,dd = key % 10;
                int ee = tx / 1000,ff = tx % 1000 / 100,gg = tx % 100 / 10,hh = tx % 10;
                int same = 0;
                if (aa == ee) same++;
                if (bb == ff) same++;
                if (cc == gg) same++;
                if (dd == hh) same++;
                if (same == 3 && a[tx] == -1)
                {
                    a[tx] = 0;
                    c[i].second = tt.second + 1;
                    mmp.push(p(tx,c[i].second));
                }
            }
        }
        for (int i = 0;i < sum;i++)
            if (c[i].first == n)
        {
            printf("%d\n",c[i].second);
            break;
        }
    }
    return 0;
}

fzu2150 fire game
题意：
有一块田，田里要么是草，要么是空的，现在有两个人，他们想玩游戏（2333玄学游戏，就必须把田里的草烧光，两个人放火选的位置是随机的，问他们是否能玩游戏，可以就输出最短时间。
思路：
开始想的是dfs，死活想不通，以为是随机选取两片草地，同时dfs，但是这样子我就不知道怎么操作了。。。后来看了题解，原来是bfs，只是把每两个格子的组合提出来，两个起点的bfs，队列为空时，记录时间。
囧：又忘记初始化vis数组，卡了10分钟，记住记住记住！！！！
代码：

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
struct node
{
    int x,y;
    int t;
};
typedef struct node node;
typedef pair<int,int> p;
p mp[105];
char a[15][15];
bool vis[15][15];
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
int main()
{
    int t;
    int cas = 1;
    scanf("%d",&t);
    while (t--)
    {
        memset(a,0,sizeof(a));
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i = 0;i < n;i++)
            for (int j = 0;j < m;j++)
            scanf(" %c",&a[i][j]);
        printf("Case %d: ",cas++);
        int sum = 0;
        for (int i = 0;i < n;i++)
            for (int j = 0;j < m;j++)
            if (a[i][j] == '#')
        {
            mp[sum].first = i;
            mp[sum].second = j;
            sum++;
        }
        if (sum == 1)
        {
            printf("0\n");
            continue;
        }
        int ans = 1000000;
        int res;
        for (int i = 0;i < sum;i++)
            for (int j = i+1;j < sum;j++)
        {
            memset(vis,0,sizeof(vis));
            int number = 2;
            node s1,s2;
            s1.t = 0,s1.x = mp[i].first,s1.y = mp[i].second;
            s2.t = 0,s2.x = mp[j].first,s2.y = mp[j].second;
            vis[s1.x][s1.y] = 1;
            vis[s2.x][s2.y] = 1;
            queue<node> mmp;
            mmp.push(s1);mmp.push(s2);
            while (mmp.size())
            {
                node tt = mmp.front();
                mmp.pop();
                for (int k = 0;k < 4;k++)
                {
                    int tx = tt.x + dx[k],ty = tt.y + dy[k];
                    if (tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty] && a[tx][ty] == '#')
                    {
                        vis[tx][ty] = 1;
                        node pp;
                        pp.t = tt.t + 1,pp.x = tx,pp.y = ty;
                        number++;
                        mmp.push(pp);
                    }
                }
                if (!mmp.size())
                {
                    res = tt.t;
                }
            }
            if (number < sum) continue;
            else
            {
                if (res < ans) ans = res;
            }
        }
        if (ans == 1000000)
            printf("-1\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}

poj3279 fliptile
题意：
有一个n*m的棋盘，上面放有白色的棋子和黑色的棋子，棋子有两面，白色为1，黑色为0，现在，要想办法把整个棋盘变成黑色的，问是否可能以及最少的步数，如果有最少步数相同的翻法，那么就输出字典序最小的翻法。翻棋子的时候，以当前翻的棋子为中心的棋子周围的棋子都会被翻，相当于5连块。
思路：
想了很久，都不知道，于是去看了题解。
第一个没想通的点是，怎样决定从哪里开始翻，原来是第一行的颜色确定了，那么整个棋盘的颜色也就确定了。因为每次决定是否翻一个棋子的时候，是由它上面的棋子是否为白色决定的，当我们翻完最后一行时，前面的所有行都是黑色的，我们只需检查最后一行是否全黑就行了。所以只需列举第一行的所有反转情况。
第二个，是学到了关于用位操作模拟路径压缩的问题。这个题，我们一共有m列，那么第一行的反转情况一共有2^m次方种，用<<比pow要快，而且很方便。我们通过左移操作来模拟第一行是否反转的情况，比如，当m为4的时候，第一行可以有0001,0010,0100,1000,0011,0111等16种不同的情况，我们1来表示反转，用0表示不反转，这样的话就很方便了。那么，我们如何考察哪一位为1呢，同样很方便。再次运用为操作，比如当m为4的时候，我们用0001,0010,0100,1000去与我们所列举的第一行的情况i进行与运算，则为真的位，就是1。比如当i为5，即0101的时候，我们通过与运算就可以知道第二个棋子和第四个棋子是要反转的。Got it？
如何记录字典序呢，只需要把步数最小（是<哦，不是<=）的时候，把相应的i，即第一行的反转操作记录下来，那么最后在进行一次i的反转就可以了。
代码：

#include <stdio.h>
#include <string.h>
int mp[20][20];
int t[20][20],f[20][20];
int m,n;
int res;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
void flip(int x,int y)
{
    res++;f[x][y] = 1;
    t[x][y] = !t[x][y];
    for (int i = 0;i < 4;i++)
    {
        int tx = x + dx[i],ty = y + dy[i];
        if (tx >= 0 && tx < m && ty >= 0 && ty < n) t[tx][ty] ^= 1;
    }
}
bool ok(int k)
{
    res = 0;
    memcpy(t,mp,sizeof(mp));
    memset(f,0,sizeof(f));
    for (int i = 0;i < m;i++)
    {
        if (k & (1 << (m-i-1)))
            flip(0,i);
    }
    for (int i = 1;i < m;i++)
        for (int j = 0;j < n;j++)
        if (t[i-1][j]) flip(i,j);
    for (int i = 0;i < n;i++)
        if (t[m-1][i]) return false;
    return true;
}
int main()
{
    while (scanf("%d%d",&m,&n) != EOF)
    {
        memset(f,0,sizeof(0));
        memset(mp,0,sizeof(0));
        memset(t,0,sizeof(0));
        for (int i = 0;i < m;i++)
            for (int j = 0;j < n;j++)
            scanf("%d",&mp[i][j]);
        int ans = 100000,p = -1;
        for (int i = 0;i < (2 << m);i++)
        {
            if (ok(i) && res < ans)
            {
                ans = res,p = i;
            }
        }
        if (p != -1)
        {
            ok(p);
            for (int i = 0;i < m;i++)
            {
                for (int j = 0;j < n;j++)
                {
                    if (!j) printf("%d",f[i][j]);
                    else printf(" %d",f[i][j]);
                }
                printf("\n");
            }
        }
        else
        {
            printf("IMPOSSIBLE\n");
        }
    }
    return 0;
}

uva11624：fire
题意：
给出一个n*m的格子，里面有墙，有人（只有一个），有fire（可能有很多个），有可走的道路。人只要能在火烧到之前到达任意边界就可以逃出，问人是否能逃出以及所用的最少时间。
思路：
两次dfs，第一次记录火到达所有点的最少时间。第二次搜索人是否能在火到达之前达到边界。
坑：
判断边界的时候，假如输入是n排m列，那么就是x小于n，y小于m，结果我把它当成数学里面的坐标来想去了。。。23wa，想吐血啊，记住教训，保险起见，画图吧！
代码：

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int maxn = 1010;
int a[maxn][maxn];
int b[maxn][maxn];
char mp[maxn][maxn];
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
typedef pair<int,int> p;
queue<p> mmp;
int m,n;
void bfs1(void)
{
    while (mmp.size()) mmp.pop();
    for (int i = 0;i < n;i++)
        for (int j = 0;j < m;j++)
    {
        if (mp[i][j] == 'F')
        {
            a[i][j] = 0;
            mmp.push(p(i,j));
        }
    }
    while (mmp.size())
    {
        p ss = mmp.front();
        mmp.pop();
        int x = ss.first,y = ss.second;
        for (int i = 0;i < 4;i++)
        {
            int nx = x + dx[i],ny = y + dy[i];
            if (nx <0 || nx >= n) continue;
            if (ny <0 || ny >= m) continue;
            if (mp[nx][ny] == '#') continue;
            if (a[nx][ny] != -1) continue;
            a[nx][ny] = a[x][y] + 1;
            mmp.push(p(nx,ny));
        }
    }
    return;
}
int bfs2(void)
{
    while (mmp.size()) mmp.pop();
    for (int i = 0;i < n;i++)
        for (int j = 0;j < m;j++)
        {
            if (mp[i][j] == 'J')
            {
                mmp.push(p(i,j));
                b[i][j] = 0;
            }
        }
    while (mmp.size())
    {
        p ss = mmp.front();
        mmp.pop();
        int x = ss.first,y = ss.second;
        if (x == 0 || x == n-1 || y == 0 || y == m-1)
        {
            return b[x][y] + 1;
        }
        for (int i = 0;i < 4;i++)
        {
            int nx = x + dx[i],ny = y + dy[i];
            if (nx <0 || nx >= n) continue;
            if (ny <0 || ny >= m) continue;
            if (mp[nx][ny] == '#') continue;
            if (b[nx][ny] != -1) continue;
            if (a[nx][ny] != -1 && b[x][y] + 1 >= a[nx][ny]) continue;
            b[nx][ny] = b[x][y] + 1;
            mmp.push(p(nx,ny));
        }
    }
    return -1;
}
int main()
{
    int t;
    scanf ("%d",&t);
    while (t--)
    {
        scanf("%d%d",&n,&m);
        memset(b,-1,sizeof(b));
        memset(a,-1,sizeof(a));
        memset(mp,0,sizeof(mp));
        for (int i = 0;i < n;i++)
            for (int j = 0;j < m;j++)
            scanf(" %c",&mp[i][j]);
        int ans = -1;
        bfs1();
        ans = bfs2();
        if (ans == -1) printf("IMPOSSIBLE\n");
        else printf("%d\n",ans);
    }
    return 0;
}

[kuangbin带我飞]专题一 简单搜索

内容目录

[kuangbin带我飞]专题一简单搜索