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

C ++ 果断超时 最朴素的方法G++ 水过

Posted by zspzspzsp at 2015-03-20 20:14:49 on Problem 1324
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string>
#include<string.h>
using namespace std;
int dx[4] = {1, -1, 0, 0};
int n, m, k;
int dy[4] = {0, 0, 1, -1};
bool mark[22][22][1 << 14];
bool shi[22][22];
struct Node 
{
    int x, y;
    int dir, step;       
}st; 
int poww(int x, int i)
{
    int sum = 1;
    for(int j = 0; j < i; j ++)
    {
      sum *= x;         
    }    
    return sum;
}
void bfs(Node st)
{
    queue<Node> p;
    p.push(st);
    mark[st.x][st.y][st.dir] = 1;
    Node v, vn;
    int dirr[10];
    bool yuan[22][22]; 
    
    while(!p.empty())
    {
        memset(dirr, 0, sizeof(dirr));
        vn = p.front();
        p.pop();
        if(vn.x == 0 && vn.y == 0)  
        {
         printf("%d\n", vn.step);
         return;
        }      
        int count = k - 2, flag = vn.dir;
        while(flag)
        {
           dirr[count--] = flag % 4;
           flag /= 4;           
        }         
        int xx = vn.x, yy = vn.y, x, y;
        memset(yuan, 0, sizeof(yuan));
        for(int i = 0; i < k - 1; i++)
        {
            
            x = xx - dx[dirr[i]];
            y = yy - dy[dirr[i]];  
            xx = x, yy = y;
            yuan[xx][yy] = 1;        
        }   
        for(int i = 0; i < 4; i++)
        {
            int flagg = 0;
            v.x = vn.x + dx[i];
            v.y = vn.y + dy[i];
            v.step = vn.step + 1;
            v.dir = 0;
            for(int j = 0; j < k - 2; j++)
            {
              v.dir += poww(4, k - 3 - j) * dirr[j];       
            }
            v.dir += poww(4, k - 2) * i;
            if(v.x >= n || v.x < 0 || v.y >= m || v.y < 0)  continue;
            if(mark[v.x][v.y][v.dir])   continue;
            if(yuan[v.x][v.y])  continue;
            if(shi[v.x][v.y])  continue;
            p.push(v);
            mark[v.x][v.y][v.dir] = 1;
        }            
    }     
 printf("-1\n");
 return;
}
int main()
{
    int a, b, x, y, p, qq = 1;
    while(scanf("%d %d", &n, &m)!=EOF)
    {
        scanf("%d", &k);
        if(n == 0 && m == 0 && k == 0)  break;
        memset(mark, 0, sizeof(mark));
        memset(shi, 0, sizeof(shi));
        scanf("%d %d", &a, &b);
        a--, b--;
        st.x = a, st.y = b;
        int step = 0, flag; 
        for(int i = 0; i < k - 1; i++)
        {
          scanf("%d %d", &x, &y);
          x-- , y--;
          if(x < a)  flag = 0;
          if(x > a)  flag = 1;
          if(y < b)  flag = 2;
          if(y > b)  flag = 3; 
          step += poww(4, k - 2 - i) * flag;
          a = x, b = y;
        }     
        st.dir = step;
        st.step = 0;       
        scanf("%d", &p);
        for(int i = 0; i < p; i++)
        {
           scanf("%d %d", &x, &y); 
           x--, y--;
           shi[x][y] = 1;       
        }    
        printf("Case %d: ", qq++);
        bfs(st);
    }    
} 

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