Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
第一道双向廣搜 3520K 32MS#include <iostream> #include <stdio.h> #include <queue> #include <vector> using namespace std; struct slt{ int state[4]; void sort(); }; bool operator==(const slt &s1, const slt &s2){ return s1.state[0] == s2.state[0] && s1.state[1] == s2.state[1] && s1.state[2] == s2.state[2] && s1.state[3] == s2.state[3]; } void slt::sort(){ for(int i = 1; i < 4; i++){ for(int j = i; j > 0; j--){ if(state[j] > state[j-1]) break; int temp = state[j]; state[j] = state[j-1]; state[j-1] = temp; } } } bool get1[64][64][64][64] = {0}, get2[64][64][64][64] = {0}; slt s[4][5000], t[4][5000]; int sNum[4] = {0}, tNum[4] = {0}; bool getNewSlt(slt oldSlt, slt &newSlt, int idx, int fx){ bool has[8][8] = {0}; for(int i = 0; i < 4; i++){ has[oldSlt.state[i]/8][oldSlt.state[i]%8] = 1; } newSlt = oldSlt; int x = oldSlt.state[idx]/8, y = oldSlt.state[idx]%8; if(fx == 0){ if(x < 1 || (x == 1 && has[x-1][y]) || (has[x-1][y] && has[x-2][y])){ return false; } if(!has[x-1][y]){ newSlt.state[idx] -= 8; } else{ newSlt.state[idx] -= 16; } newSlt.sort(); return true; } else if(fx == 1){ if(y > 6 || (y == 6 && has[x][y+1]) || (has[x][y+1] && has[x][y+2])){ return false; } if(!has[x][y+1]) newSlt.state[idx] += 1; else newSlt.state[idx] += 2; newSlt.sort(); return true; } else if(fx == 2){ if(x > 6 || (x == 6 && has[x+1][y]) || (has[x+1][y] && has[x+2][y])){ return false; } if(!has[x+1][y]) newSlt.state[idx] += 8; else newSlt.state[idx] += 16; newSlt.sort(); return true; } else{ if(y < 1 || (y == 1 && has[x][y-1]) || (has[x][y-1] && has[x][y-2])){ return false; } if(!has[x][y-1]) newSlt.state[idx] -= 1; else newSlt.state[idx] -= 2; newSlt.sort(); return true; } } int main() { slt first, second; for(int i = 0; i < 4; i++){ int x,y; scanf("%d%d", &x, &y); first.state[i] = 8 * (x-1) + (y-1); } for(int i = 0; i < 4; i++){ int x,y; scanf("%d%d", &x, &y); second.state[i] = 8 * (x-1) + (y-1); } first.sort(); second.sort(); if(first == second){ printf("YES\n"); return 0; } sNum[0] = 1, tNum[0] = 1; s[0][0] = first, t[0][0] = second; get1[first.state[0]][first.state[1]][first.state[2]][first.state[3]] = 1; get2[second.state[0]][second.state[1]][second.state[2]][second.state[3]] = 1; for(int i = 0; i < 4; i++){ for(int j = 0; j < sNum[i]; j++){ //slt temp = s[i][j]; slt newSlt; for(int k = 0; k < 4; k++){ for(int l = 0; l < 4; l++){ if(getNewSlt(s[i][j], newSlt, k, l)){ if(get1[newSlt.state[0]][newSlt.state[1]][newSlt.state[2]][newSlt.state[3]]){ continue; } get1[newSlt.state[0]][newSlt.state[1]][newSlt.state[2]][newSlt.state[3]] = 1; if(i < 3){ s[i+1][sNum[i+1]] = newSlt; sNum[i+1] ++; } } } } } } for(int i = 0; i < 4; i++){ for(int j = 0; j < tNum[i]; j++){ //slt temp = s[i][j]; slt newSlt; for(int k = 0; k < 4; k++){ for(int l = 0; l < 4; l++){ if(getNewSlt(t[i][j], newSlt, k, l)){ if(get1[newSlt.state[0]][newSlt.state[1]][newSlt.state[2]][newSlt.state[3]]){ printf("YES\n"); return 0; } if(get2[newSlt.state[0]][newSlt.state[1]][newSlt.state[2]][newSlt.state[3]]){ continue; } get2[newSlt.state[0]][newSlt.state[1]][newSlt.state[2]][newSlt.state[3]] = 1; if(i < 3){ t[i+1][tNum[i+1]] = newSlt; tNum[i+1] ++; } } } } } } printf("NO\n"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator