Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

分享刘汝佳大神的代码,英文是刘汝佳大神的注释,中文是我自己加的注释

Posted by sapphirebitter at 2017-08-31 17:25:02 on Problem 3523
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
using namespace std;

const int maxs = 20;
const int maxn = 150; /// 75% cells plus 2 fake nodes
const int dx[]= {1,-1,0,0,0}; /// 4 moves, plus "no move"
const int dy[]= {0,0,1,-1,0};

inline int ID(int a, int b, int c)
{
    return (a<<16)|(b<<8)|c;///由于int 类型保存8个字节,所以这个操作将a放到了最前面的8个字节,b放到了中间的8个字节,c放到了最后的8个字节
}

int s[3], t[3]; /// starting/ending position of each ghost

int deg[maxn], G[maxn][5]; /// target cells for each move (including "no move").deg 表示出度,存储能够前进的方向

inline bool conflict(int a, int b, int a2, int b2)
{
    return a2 == b2 || (a2 == b && b2 == a);///第一个表示a,b进入同一空格,第二个表示2者交换位置
}

int d[maxn][maxn][maxn]; /// distance from starting state

int bfs()
{
    queue<int> q;
    memset(d, -1, sizeof(d));
    q.push(ID(s[0], s[1], s[2])); /// starting node
    d[s[0]][s[1]][s[2]] = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        int a = u>>16, b = (u>>8)&0xff, c = u&0xff;///&0xff表示取最后的8个字节
        if(a == t[0] && b == t[1] && c == t[2]) return d[a][b][c]; /// solution found
        for(int i = 0; i < deg[a]; i++)
        {
            int a2 = G[a][i];
            for(int j = 0; j < deg[b]; j++)
            {
                int b2 = G[b][j];
                if(conflict(a, b, a2, b2)) continue;
                for(int k = 0; k < deg[c]; k++)
                {
                    int c2 = G[c][k];
                    if(conflict(a, c, a2, c2)) continue;
                    if(conflict(b, c, b2, c2)) continue;
                    if(d[a2][b2][c2] != -1) continue;///判断是否被访问过
                    d[a2][b2][c2] = d[a][b][c]+1;
                    q.push(ID(a2, b2, c2));
                }
            }
        }
    }
    return -1;
}

int main()
{
    int w, h, n;

    while(scanf("%d%d%d\n", &w, &h, &n) == 3 && n)
    {
        char maze[20][20];
        for(int i = 0; i < h; i++)
            fgets(maze[i], 20, stdin);

        /// extract empty cells
        int cnt, x[maxn], y[maxn], id[maxs][maxs]; ///cnt is the number of empty cells
        cnt = 0;
        for(int i = 0; i < h; i++)
            for(int j = 0; j < w; j++)
                if(maze[i][j] != '#')
                {
                    x[cnt] = i;
                    y[cnt] = j;
                    id[i][j] = cnt;
                    if(islower(maze[i][j])) s[maze[i][j] - 'a'] = cnt;
                    else if(isupper(maze[i][j])) t[maze[i][j] - 'A'] = cnt;
                    cnt++;
                }

        /// build a graph of empty cells
        for(int i = 0; i < cnt; i++)
        {
            deg[i] = 0;
            for(int dir = 0; dir < 5; dir++)
            {
                int nx = x[i]+dx[dir], ny = y[i]+dy[dir];
                /// "Outermost cells of a map are walls" means we don't need to check out-of-bound
                if(maze[nx][ny] != '#') G[i][deg[i]++] = id[nx][ny];///出度+1,指向空格区域
            }
        }

        /// add fakes nodes so that in each case we have 3 ghosts. this makes the code shorter
        if(n <= 2)
        {
            deg[cnt] = 1;
            G[cnt][0] = cnt;
            s[2] = t[2] = cnt++;
        }
        if(n <= 1)
        {
            deg[cnt] = 1;
            G[cnt][0] = cnt;
            s[1] = t[1] = cnt++;
        }

        printf("%d\n", bfs());
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator