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 |
110120_119#include<cstdio> #pragma warning (disable:4996) using namespace std; int col, row; int minStep; //最小步数 int field[110][110]; //存储地图 int direction[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; //方向 void dfs(int x, int y, int step) { if (step > 10 || step > minStep) return; for (int i = 0; i < 4; i++) { int nx = x + direction[i][0]; //先选择一个方向让石头飞 int ny = y + direction[i][1]; //printf("xyi: %d %d %d\n", x, y, i); while (0 <= nx && nx < row && 0 <= ny && ny < col) //只要没有越界就让石头一直飞 { //对飞行过程中可能出现的情况做判断 switch (field[nx][ny]) { case 0: //空地情况 nx += direction[i][0]; //朝当前的方向继续飞 ny += direction[i][1]; break; case 3: //到达终点 if (step + 1 < minStep) //若当前步数小于最小步数,则更新步数 minStep = step + 1; return; case 1: //遇到了石头,分为两种情况,一是:相邻石头(不可以撞碎),二是:飞行过程中遇到石头,则撞碎 if (!(nx - direction[i][0] == x && ny - direction[i][1] == y)) //若后退一步不是初始位置,说明不是相邻石头 { field[nx][ny] = 0; //不是相邻石头则将其变成空地 dfs(nx - direction[i][0], ny - direction[i][1], step + 1); //后退一步,再次深搜,步数加1 field[nx][ny] = 1; //刚才的石头需要复原,供下一次尝试 } nx = -1; //不论是否是相邻石头,只要碰到石头,则需要换方向,此时需要破坏掉while中的条件,使while循环终止,继续进行for循环 break; } } } } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int sx, sy; while (scanf("%d %d", &col, &row) != EOF) { if (col == 0 && row == 0) return 0; minStep = 11; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { scanf("%d", &field[i][j]); if (field[i][j] == 2) //记录开始位置 { sx = i; sy = j; field[i][j] = 0; //将开始的点变为空地 } } } dfs(sx, sy, 0); if (minStep > 10) minStep = -1; //步数大于10步则说明不可以到达终点 printf("%d\n", minStep); //打印最小步数 } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator