现在的位置: 首页 > 综合 > 正文

poj 3414 Pots(TLE代码),回头继续搞

2018年04月23日 ⁄ 综合 ⁄ 共 2275字 ⁄ 字号 评论关闭

我比较懒,直接用string记录路径,可是是因为这个地方超时。。。

#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <ctime>
#define LL long long
#define Vi vector<int>
#define Si set<int>
#define readf freopen("input.txt","r",stdin)
#define writef freopen("output.txt","w",stdout)
#define FU(i,a) for(int i(1); i <= (a); i++)
#define FD(i,a) for(int i(a); i >= (1); i--)
#define FOR(i,a,b) for(int i(a);i <= (b); i++)
#define FORD(i,a,b) for(int i(a);i >= (b); i--)
#define SET(a,b) memset(a,b,sizeof(a))
#define SD(a) scanf("%d",&(a))
#define LN printf("\n")
#define PS printf(" ")
#define pb push_back
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const double pi = acos(-1.0);
const int maxn = 2000;
const int INF = 99999999;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
using namespace std;
int a,b,c;
bool visit[200][200];
struct state{
    int i,j,step;
    string path;
}q[20000],ans;7
bool bfs(){
    int head,rear;
    head=rear=0;
    q[rear].i=0;
    q[rear].step=0;
    q[rear++].j=0;
    visit[0][0]=false;
    while(head<rear){
        state tmp=q[head++];
        if(tmp.i==c || tmp.j==c){
            ans=tmp;
            return true;
        }
        if(!visit[a][tmp.j]){
            q[rear].i=a;
            q[rear].j=tmp.j;
            q[rear].step=tmp.step+1;
            q[rear++].path=tmp.path+"FILL(1)\n";
            visit[a][tmp.j]=true;
        }
        if(!visit[tmp.i][b]){
            q[rear].i=tmp.i;
            q[rear].j=b;
            q[rear].step=tmp.step+1;
            q[rear++].path=tmp.path+"FILL(2)\n";
            visit[tmp.i][b]=true;
        }
        int x=tmp.i+tmp.j,t1,t2;
        if(x>a){
            t2=tmp.j-(a-tmp.i);
            t1=a;
        }else{
            t1=x;
            t2=0;
        }
        if(!visit[t1][t2]){
            q[rear].i=t1;
            q[rear].j=t2;
            q[rear].step=tmp.step+1;
            q[rear++].path=tmp.path+"POUR(2,1)\n";
            visit[t1][t2]=true;
        }
        if(x>b){
            t1=tmp.i-(b-tmp.j);
            t2=b;
        }else{
            t2=x;
            t1=0;
        }
        if(!visit[t1][t2]){
            q[rear].i=t1;
            q[rear].j=t2;
            q[rear].step=tmp.step+1;
            q[rear++].path=tmp.path+"POUR(1,2)\n";
            visit[t1][t2]=true;
        }
        if(!visit[0][tmp.j]){
            q[rear].i=0;
            q[rear].j=tmp.j;
            q[rear].step=tmp.step+1;
            q[rear++].path=tmp.path+"DROP(1)\n";
            visit[0][tmp.j]=true;
        }
        if(!visit[tmp.i][0]){
            q[rear].i=tmp.i;
            q[rear].j=0;
            q[rear].step=tmp.step+1;
            q[rear++].path=tmp.path+"DROP(2)\n";
            visit[tmp.i][0]=true;
        }
    }
    return false;
}
int main()
{
    SD(a);
    SD(b);
    SD(c);
    if(a % 2 == 0 && b % 2 == 0 && c % 2 != 0) {    //剪枝     老天&&打成%。。。。。。。
        cout << "impossible" << endl;
        return 0;
    }
    if(c > a && c > b) {                      //剪枝
        cout << "impossible" << endl;
        return 0;
    }
    bool flag=bfs();
    if(flag){
        cout<<ans.step<<endl;
        cout<<ans.path;
    }else{
        cout<<"impossible"<<endl;
    }
	return 0;
}






【上篇】
【下篇】

抱歉!评论已关闭.