y行x列,傻傻分不清楚。
ans[ i ][ j ][ k ][ d ] 標記是否以 轉彎k次且方向為d 的狀態走過。
被學弟蔑視的一道題竟然沒能1A,老啦。
#include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long int #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 1000000007 #define LM(a,b) (((ULL)(a))<<(b)) #define RM(a,b) (((ULL)(a))>>(b)) using namespace std; char Map[110][110]; bool ans[110][110][11][4]; struct Q { int x,y,d,ans; }; int jx[] = {-1, 0, 1, 0}; int jy[] = { 0,-1, 0, 1}; void bfs(int n,int m) { int sx,sy,ex,ey,k; scanf("%d %d %d %d %d",&k,&sy,&sx,&ey,&ex); queue q; Q f,t; f.x = sx; f.y = sy; f.d = -1; f.ans = -1; q.push(f); while(q.empty() == false) { f = q.front(); q.pop(); if(f.x == ex && f.y == ey) { printf("yes\n"); return ; } for(int i = 0;i < 4; ++i) { t.x = f.x + jx[i]; t.y = f.y + jy[i]; t.d = i; if(f.d == i) t.ans = f.ans; else t.ans = f.ans+1; if(1 <= t.x && t.x <= n && 1 <= t.y && t.y <= m && t.ans <= k && '.' == Map[t.x][t.y] && ans[t.x][t.y][t.ans][t.d] == false) { ans[t.x][t.y][t.ans][t.d] = true; q.push(t); } } } printf("no\n"); return ; } int main() { int T; scanf("%d",&T); int n,m,i; while(T--) { scanf("%d %d",&n,&m); memset(ans,false,sizeof(ans)); for(i = 1;i <= n; ++i) scanf("%*c%s",Map[i]+1); bfs(n,m); } } //const int MAXN = 1000010; // //struct Edge //{ // int u,v,w,next; //} edge[MAXN*2]; // //int head[MAXN]; // //int Top; // //void Link(int u,int v,int w = -1) //{ // edge[Top].u = u; // edge[Top].v = v; // edge[Top].w = w; // edge[Top].next = head[u]; // head[u] = Top++; //} // //void Init(int n) //{ // Top = 0; // memset(head,-1,sizeof(int)*(n+2)); //} // //struct Q //{ // int v,w; // // bool operator < (const Q &a) const // { // return w < a.w; // } //}; //
q; Q f,t; f.x = sx; f.y = sy; f.d = -1; f.ans = -1; q.push(f); while(q.empty() == false) { f = q.front(); q.pop(); if(f.x == ex && f.y == ey) { printf("yes\n"); return ; } for(int i = 0;i < 4; ++i) { t.x = f.x + jx[i]; t.y = f.y + jy[i]; t.d = i; if(f.d == i) t.ans = f.ans; else t.ans = f.ans+1; if(1 <= t.x && t.x <= n && 1 <= t.y && t.y <= m && t.ans <= k && '.' == Map[t.x][t.y] && ans[t.x][t.y][t.ans][t.d] == false) { ans[t.x][t.y][t.ans][t.d] = true; q.push(t); } } } printf("no\n"); return ; } int main() { int T; scanf("%d",&T); int n,m,i; while(T--) { scanf("%d %d",&n,&m); memset(ans,false,sizeof(ans)); for(i = 1;i <= n; ++i) scanf("%*c%s",Map[i]+1); bfs(n,m); } } //const int MAXN = 1000010; // //struct Edge //{ // int u,v,w,next; //} edge[MAXN*2]; // //int head[MAXN]; // //int Top; // //void Link(int u,int v,int w = -1) //{ // edge[Top].u = u; // edge[Top].v = v; // edge[Top].w = w; // edge[Top].next = head[u]; // head[u] = Top++; //} // //void Init(int n) //{ // Top = 0; // memset(head,-1,sizeof(int)*(n+2)); //} // //struct Q //{ // int v,w; // // bool operator < (const Q &a) const // { // return w < a.w; // } //}; //
CodeForces 149D Coloring Brack
bzoj3095--數學題,bzoj3095--數學題目大意
POJ 1459-Power Network(網絡流_最大流
SDUT OJ 走迷宮 #include using
STL之vector使用詳解 好久不用STL了,忘的差不
B-樹 C++模板類封裝(有圖有真相),b-模板定義: 一棵