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

Re:状压BFS,时隔两个半月,二刷1A留念

Posted by renhaijiao at 2020-11-24 14:18:25 on Problem 1324
In Reply To:状压BFS,时隔两个半月,二刷1A留念 Posted by:vjubge4 at 2019-06-16 20:59:13
> #include<cstdio>
> #include<cstring>
> #include<algorithm>
> #include<queue>
> using namespace std;
> const int oo = 0x3f3f3f3f;
> int W, H;
> int field[20][20];
> int sx, sy, ss;
> int L, N;
> int dx[] = {1, 0, -1, 0};
> int dy[] = {0, -1, 0, 1};
> int dist[20][20][1 << 14];
> struct P{
>     int x, y, s;
> };
> 
> bool Judge(int nx, int ny, int x, int y, int s){
>     if(nx < 0 || nx >= H || ny <0 || ny >= W || field[nx][ny] == 1){
>         return false;
>     }
>     for(int i = 0; i < L - 1; i ++){
>         int mv = (s >> (2 * i)) & 3;
>         x = x + dx[mv];
>         y = y + dy[mv];
>         if(nx == x && ny == y){
>             return false;
>         }
>     }
>     return true;
> }
> 
> int bfs(){
>     memset(dist, oo, sizeof(dist));
>     dist[sx][sy][ss] = 0;
>     queue<P> que;
>     que.push((P){sx, sy, ss});
>     while(!que.empty()){
>         P p = que.front();
>         que.pop();
>         if(p.x == 0 && p.y == 0){
>             return dist[p.x][p.y][p.s];
>         }
>         for(int i =0; i < 4; i ++){
>             int nx = p.x + dx[i];
>             int ny = p.y + dy[i];
>             int ns = p.s;
>             if(Judge(nx, ny, p.x, p.y, p.s)){
>                 ns = (ns << 2) + (i + 2) % 4;
>                 ns &= (1 << ((L - 1) * 2)) - 1;
>                 if(dist[nx][ny][ns] > dist[p.x][p.y][p.s] + 1){
>                     dist[nx][ny][ns] = dist[p.x][p.y][p.s] + 1;
>                     que.push((P){nx, ny, ns});
>                 }
>             }
>         }
>     }
>     return -1;
> }
> 
> int main(){
>     int c = 0;
>     while(true){
>         scanf("%d %d %d", &H, &W, &L);
>         if(H == 0 && W == 0 && L == 0){
>             break;
>         }
>         memset(field, 0, sizeof(field));
>         pair<int, int> arr[8];
>         for(int i = 0; i < L; i ++){
>             scanf("%d %d", &arr[i].first, &arr[i].second);
>             arr[i].first --;
>             arr[i].second --;
>         }
>         sx = arr[0].first;
>         sy = arr[0].second;
>         ss = 0;
>         for(int i = L - 1; i > 0; i --){
>             ss <<= 2;
>             if(arr[i].second == arr[i - 1].second){
>                 if(arr[i].first == arr[i - 1].first + 1){
>                     ss += 0;
>                 } else {
>                     ss += 2;
>                 }
>             } else {
>                 if(arr[i].second == arr[i - 1].second - 1){
>                     ss += 1;
>                 } else {
>                     ss += 3;
>                 }
>             }
>         }
>         scanf("%d", &N);
>         int a, b;
>         for(int i =0; i < N; i ++){
>             scanf("%d %d", &a, &b);
>             field[a - 1][b - 1] = 1;
>         }
>         printf("Case %d: %d\n", ++c, bfs());
>     }
> }

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