北京海淀房管局网站,网站开发交流群,免费的舆情网站,做网站销售提成怎么算牛和农夫按照固定的走法在10x10的地图中走#xff0c;每分钟走一步#xff0c;求经过几分钟相遇。永远不能相遇输出0. 纯模拟的题。 判断永远不能相遇的方法是如果遇到了一个先前的状态#xff0c;那么肯定存在循环#xff0c;必定不能相遇。 程序中把状态表示为牛和农夫的…牛和农夫按照固定的走法在10x10的地图中走每分钟走一步求经过几分钟相遇。永远不能相遇输出0. 纯模拟的题。 判断永远不能相遇的方法是如果遇到了一个先前的状态那么肯定存在循环必定不能相遇。 程序中把状态表示为牛和农夫的位置以及面向的方向通过map判断是否遇到重复状态因为map中不存在的键会有默认值对于bool来说就是false。 一点点空间的优化是地图只用存一份牛和农夫不显示在地图上尽通过状态里的点间接表示。 View Code 1 /*2 ID: xjtuacm13 PROG: ttwo4 LANG: C5 */6 #includeiostream7 #includestack8 #includecstring9 #includecstdio10 #includequeue11 #includealgorithm12 #includemap13 using namespace std;14 15 const int N 10;16 enum direction {NORTH, EAST, SOUTH, WEST};17 18 struct point19 {20 int x, y;21 point(int xx 0, int yy 0) :x(xx), y(yy) {}22 void set(int xx, int yy)23 {24 x xx;25 y yy;26 }27 bool operator(const point pt) const28 {29 return x pt.x y pt.y;30 }31 };32 33 struct state34 {35 int d[2];36 point pt[2];37 state() { d[0] d[1] NORTH; }38 39 bool operator(const state s) const40 {41 return memcmp(this, s, sizeof(state)) 0;42 }43 };44 45 mapstate, bool h;46 char pane[N][N];47 48 inline bool inRange(point pt)49 {50 return pt.x 051 pt.x 1052 pt.y 053 pt.y 10;54 }55 56 bool met(const state s)57 {58 return s.pt[0] s.pt[1];59 }60 61 void next(state s)62 {63 point npt[2];64 65 for(int i 0; i! 2; i)66 {67 switch(s.d[i])68 {69 case NORTH:70 npt[i].set(s.pt[i].x - 1, s.pt[i].y);71 break;72 case EAST:73 npt[i].set(s.pt[i].x, s.pt[i].y 1);74 break;75 case SOUTH:76 npt[i].set(s.pt[i].x 1, s.pt[i].y);77 break;78 case WEST:79 npt[i].set(s.pt[i].x, s.pt[i].y - 1);80 break;81 }82 83 if(inRange(npt[i])84 pane[npt[i].x][npt[i].y] ! *)85 {86 s.pt[i] npt[i];87 }88 else89 {90 s.d[i] 1;91 s.d[i] % 4;92 }93 }94 }95 96 int main(int argc, char *argv[])97 {98 freopen(ttwo.in, r, stdin);99 #ifndef USACO
100 freopen(ttwo.out, w, stdout);
101 #endif // USACO
102
103 state s;
104
105 for(int i 0; i! N; i)
106 for(int j 0; j! N; j)
107 {
108 scanf(%c, pane[i][j]);
109 if(pane[i][j] \n)
110 scanf(%c, pane[i][j]);
111
112 if(pane[i][j] F
113 || pane[i][j] C)
114 {
115 int t (pane[i][j] - C 0 ? 0 : 1);
116 s.pt[t].set(i, j);
117 pane[i][j] .;
118 }
119 }
120
121 int minute 0;
122 h[s] true;
123 while(!met(s))
124 {
125 next(s);
126 if(h[s])
127 {
128 printf(0\n);
129 return 0;
130 }
131
132 h[s] true;
133 minute;
134 }
135
136 printf(%d\n, minute);
137
138 return 0;
139 } BTW纯模拟真心考验细心程度 。。。。转载于:https://www.cnblogs.com/tech-cabin/archive/2013/02/05/2893386.html
