2017-11-16 21:05:15

_一个提高D1T2莫名炸了的蒟蒻写写普及_

#include <cstdio>
#include <cctype>
#include <cstring>
#include <deque>
using namespace std;
#define MAXN 105
#define MAXM 100010
#define MAXP 100100
char buf[1000001], *p1 = buf, *p2 = buf;
inline char get_char(){
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
int num = 0;
char c;
while(isspace(c = get_char()));
while(num = num * 10 + c - 48, isdigit(c = get_char()));
return num;
}
inline int min(int a, int b){
int c = (a - b) >> 31;
return (a & c) | (b & ~ c);
}
int n, m, tot = 1, dis[MAXM];
int beginx[MAXM], endx[MAXM], nxt[MAXM], h;
bool has[MAXM], vis[MAXM];
short matrix[MAXN][MAXN];
inline int Get_Pos(int i, int j){
return ((i - 1) * n + j - 1) << 1;
}
inline void add_edge(int u, int v, bool c){
nxt[++tot] = beginx[u], beginx[u] = tot, endx[tot] = v, has[tot] = c;
nxt[++tot] = beginx[v], beginx[v] = tot, endx[tot] = u, has[tot] = c;
}
inline void edge(int u, int v, int c){
int tmp = ++h;
switch(c){
case 2:
nxt[++tot] = beginx[u], beginx[u] = tot, endx[tot] = tmp, has[tot] = true;
nxt[++tot] = beginx[tmp], beginx[tmp] = tot, endx[tot] = v, has[tot] = true;
break;
case 3:
nxt[++tot] = beginx[u], beginx[u] = tot, endx[tot] = tmp, has[tot] = true;
nxt[++tot] = beginx[tmp], beginx[tmp] = tot, endx[tot] = tmp = ++h, has[tot] = true;
nxt[++tot] = beginx[tmp], beginx[tmp] = tot, endx[tot] = v, has[tot] = true;
break;
}
}
inline void add_edges(int u, int v, int c){
nxt[++tot] = beginx[u], beginx[u] = tot, endx[tot] = v, has[tot] = c;
edge(v, u, c + 2);
}
deque<int> mession;
inline void bfs(int s){
bool flag = matrix[n][n];
int tmp = Get_Pos(n, n) + matrix[n][n];
int tmp1 = Get_Pos(n, n) + 1, tmp2 = Get_Pos(n, n) + 2;
mession.push_back(s);
dis[s] = 0, vis[s] = true;
int u, v;
while(!mession.empty()){
u = mession.front(), mession.pop_front();
for(int i = beginx[u]; i; i = nxt[i]){
v = endx[i];
if(vis[v]) continue;
vis[v] = true;
dis[v] = dis[u] + has[i];
if(flag){
if(dis[tmp] != -1) return ;
} else if(dis[tmp1] != -1 && dis[tmp2] != -1) return ;
if(has[i] || mession.empty()) mession.push_back(v);
else mession.push_front(v);
}
}
}
int main(){
for(int i = 1; i <= m; i++){
}
h = (n * n) << 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
int tmp = matrix[i][j], t = Get_Pos(i, j) + tmp;
if(!tmp){
int tx = Get_Pos(i, j);
int tmp1 = matrix[i + 1][j], t1 = Get_Pos(i + 1, j) + tmp1, tmp2 = matrix[i][j + 1], t2 = Get_Pos(i, j + 1) + tmp2;
int tmp3 = matrix[i - 1][j], t3 = Get_Pos(i - 1, j) + tmp3, tmp4 = matrix[i][j - 1], t4 = Get_Pos(i, j - 1) + tmp4;
if(tmp1) add_edges(tx + tmp1, t1, 0), add_edges(tx + 3 - tmp1, t1, 1);
if(tmp2) add_edges(tx + tmp2, t2, 0), add_edges(tx + 3 - tmp2, t2, 1);
if(tmp3) add_edges(tx + tmp3, t3, 0), add_edges(tx + 3 - tmp3, t3, 1);
if(tmp4) add_edges(tx + tmp4, t4, 0), add_edges(tx + 3 - tmp4, t4, 1);
continue;
}
int tmp1 = matrix[i + 1][j], t1 = Get_Pos(i + 1, j) + tmp1, tmp2 = matrix[i][j + 1], t2 = Get_Pos(i, j + 1) + tmp2;
if(tmp1) add_edge(t, t1, !(tmp == tmp1));
if(tmp2) add_edge(t, t2, !(tmp == tmp2));
}
}
memset(dis, -1, sizeof(dis));
bfs(matrix[1][1]);
int tmp = Get_Pos(n, n);
if(matrix[n][n]) printf("%d", dis[tmp + matrix[n][n]]);
else printf("%d", min(dis[tmp + 1], dis[tmp + 2]));
return 0;
}

• star
首页