奇偶剪枝+ DFS
Tempter of the BoneTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 148204 Accepted Submission(s): 39516 Problem Description The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
Input The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
Output For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.
Sample Input 4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0
Sample Output NO YES
Author ZHANG, Zheng
Source
|
這道題一開始我用bfs寫，沒寫出來，用dfs寫超時，又用奇偶剪枝，
奇偶剪枝：同奇偶性的兩個數的和差一定爲偶數
從0到0必定爲偶數步數，從0到一必定爲奇數步數
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
struct node
{
int x,y;
};
int t,n,wall=0,m,dir[4][2]={{ 0, 1 }, { 1, 0 },{ 0, -1 }, { -1, 0 }};
char map[10][10];
node ve;
bool DFS(node nd, int d)
{
if (d == t&&nd.x==ve.x&&nd.y==ve.y) //路徑長度爲返回true，表示此次搜索有解
{
return true;
}
if(nd.x<1||nd.x>n||nd.y<1||nd.y>m)
{
return false;
}
int t1=abs(ve.x-nd.x);
int t2=abs(ve.y-nd.y); //這錯過
int temp=t-d-(t1+t2);
if(temp<0||temp &1 ) //數學再次發揮了作用
{
return false;
}
for(int i=0;i<4;i++)
{
if(map[nd.x+dir[i][0]][nd.y+dir[i][1]]!='X')
{
map[nd.x+dir[i][0]][nd.y+dir[i][1]]='X';
node m; //需要新生成一個節點
m.x=nd.x+dir[i][0]; //體現了編程的嚴謹性
m.y=nd.y+dir[i][1];
if(DFS(m,d+1))
{
return true;
}
map[nd.x+dir[i][0]][nd.y+dir[i][1]]='.'; //這也錯過
}
}
return false; //本次搜索無解
}
int main()
{
int i,j;
char s[10];
node vs;
while(~scanf("%d%d%d",&n,&m,&t),n||m||t)
{
getchar();
vs.x=vs.y=ve.x=ve.y=0;
wall=0;
for(i=1;i<=n;i++)
{
scanf("%s",s+1);
for(j=1;j<=m;j++)
{
map[i][j]=s[j];
if(s[j]=='S')
{
vs.x=i;
vs.y=j;
}
if(s[j]=='D')
{
ve.x=i;
ve.y=j;
}
if(s[j]=='X')
wall++;
}
}
if(n*m-wall<=t)
{
cout<<"NO"<<endl;
continue;
}
map[vs.x][vs.y]='X';
if(DFS(vs,0))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
再看看各位大神的，真的是八仙過海，各顯神通。
#include <stdio.h>
#include <iostream>
#include<math.h>
using namespace std;
char map[10][10];
int dir[4][2] =
{
{ 0, 1 }, { 1, 0 },
{ 0, -1 }, { -1, 0 }
};
struct NodeClass
{
int x;
int y;
} Start;
NodeClass End;
int N, M, T;
int wall;
bool DFS(NodeClass n, int d)
{
if (d==T&&n.x==End.x&&n.y==End.y) //一旦搜索深度到達一個結束狀態，就返回true
{
return true;
}
if (n.x>N || n.y>M || n.x <= 0 || n.y <= 0)//出界
return false;
int s1 = abs(End.x - n.x);//根據奇偶性剪枝
int s2 = abs(End.y - n.y);
int temp = T - d - (s1 + s2);
if (temp < 0 || temp & 1)
return false;
for (int i = 0; i < 4; i++) //遍歷n相鄰的節點nextNode
{
if (map[n.x + dir[i][0]][n.y + dir[i][1]] != 'X')
{
map[n.x + dir[i][0]][n.y + dir[i][1]] = 'X';//在下一步搜索中，nextNode不能再次出現
NodeClass nextNode;
nextNode.x = n.x + dir[i][0];
nextNode.y = n.y + dir[i][1];
if (DFS(nextNode, d + 1)) //如果搜索出有解
{
return true;
}
//重新設置成false，因爲它有可能出現在下一次搜索的別的路徑中
map[n.x + dir[i][0]][n.y + dir[i][1]] = '.';
}
}
return false;//本次搜索無解
}
int main()
{
while (scanf("%d%d%d", &N, &M, &T) != EOF)
{
getchar();
if (!N && !M && !T)
break;
End.x = End.y=Start.x = Start.y = wall = 0;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
scanf("%c", &map[i][j],1);
if (map[i][j] == 'S')
{
Start.x = i;
Start.y = j;
}
else if (map[i][j] == 'D')
{
End.x = i;
End.y = j;
}
else if (map[i][j] == 'X')
wall++;
}
getchar();
}
if (N*M - wall <= T)//t是代表要走的步數，步數加牆數必須小於總格子數的，因爲所有格子中還包括了S和D，這是剪枝
{
printf("NO\n");
continue;
}
map[Start.x][Start.y] = 'X';//出發點是不可能再走的了，變爲牆
if (DFS(Start, 0))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
two：
#include <cstdio>//常規dfs搜需要及時return和奇偶剪枝
char ch;
int a[10][10], f, n, m, t, si, sj, di, dj, c, i, j;
void solve(int x, int y, int t)
{
if (t == 0 && a[x][y] == -1)
f = 1;
if (t == 0) return;
a[x][y] = 0; //設爲圍牆
if (x - 1 >= 0 && a[x - 1][y]) //我第一次見這種寫法
{
solve(x - 1, y, t - 1);
if(f) return;
}
if (x + 1<n&&a[x + 1][y])
{
solve(x + 1, y, t - 1);
if (f)return;
}
if (y - 1 >= 0 && a[x][y - 1])
{
solve(x, y - 1, t - 1);
if (f)return;
}
if (y + 1<m&&a[x][y + 1])
{
solve(x, y + 1, t - 1);
if (f)return;
}
a[x][y] = 1;
}
int main()
{
while (scanf("%d%d%d", &n, &m, &t) && n)
{
getchar(), c = f = 0;
for (i = 0; i<n; i++)
{
for (j = 0; j<m; j++)
{
ch = getchar();
if (ch == '.')
c++,a[i][j] = 1;
else if (ch == 'X') //圍牆標爲零
a[i][j] = 0;
else if (ch == 'S')
si = i,sj = j;
else if (ch == 'D') //終點記爲-1
a[i][j] = -1,di = i,dj = j;
}
getchar();
}
if ((di + dj - si - sj - t) % 2 == 0 && t <= c + 1) //奇偶剪枝，最短路徑和規定的時間同奇偶性 兩個同奇偶性的數的和差一定爲偶數
solve(si, sj, t);
puts(f ? "YES" : "NO");
}
return 0;
}
three：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int N, M, T, ex, ey;
vector<string> board;
bool flag;
void DFS(int x, int y, int time)
{
if (board[x][y] == 'X') return;
if (board[x][y] == 'D' && time == T) { flag = true; return; }
if (board[x][y]=='D') return;
int val = T - time - (abs(x - ex) + abs(y - ey));
if (val < 0 || val & 1) return; //第二次剪枝
board[x][y] = 'X';
if(x>=1 && !flag) DFS(x - 1, y, time + 1);
if(x<N-1 && !flag) DFS(x + 1, y, time + 1);
if(y>=1 && !flag) DFS(x, y - 1, time + 1);
if(y<M-1 && !flag) DFS(x, y + 1, time + 1);
board[x][y] = '.';
}
int main()
{
int x, y, wall;
while (cin >> N >> M >> T)
{
if (!N && !M && !T) break;
board.clear();
board.assign(N, "");
wall = 0;
for (int i = 0; i < N; i++) // 容器裏套用string
{
cin >> board[i];
for (int j = 0; j < M; j++)
{
if (board[i][j] == 'S'){ x = i; y = j; }
if (board[i][j] == 'X') wall++;
if (board[i][j] == 'D'){ ex = i; ey = j; }
}
}
if (N*M - wall <= T) { cout << "NO\n"; continue; } //第一次剪枝，規定時間和牆數一定小於等於迷宮規模
flag = false;
board[x][y] = '.'; //此處很重要
DFS(x, y, 0);
if (flag) cout << "YES\n";
else cout << "NO\n";
}
system("pause");
return 0;
}
four：
#include<stdio.h> int T,N,M; int w; char ch[10][10]; int DFS(int x,int y,int t) { if(w==1) return 0; if(ch[x][y+1]=='D'||ch[x][y-1]=='D'||ch[x+1][y]=='D'||ch[x-1][y]=='D') { if(t==T){w=1;return 0;} } if(y+1<M&&ch[x][y+1]=='.') { ch[x][y]='X'; DFS(x,y+1,t+1); ch[x][y]='.'; } if(x+1<N&&ch[x+1][y]=='.') { ch[x][y]='X'; DFS(x+1,y,t+1); ch[x][y]='.'; } if(y-1>=0&&ch[x][y-1]=='.') { ch[x][y]='X'; DFS(x,y-1,t+1); ch[x][y]='.'; } if(x-1>=0&&ch[x-1][y]=='.') { ch[x][y]='X'; DFS(x-1,y,t+1); ch[x][y]='.'; } return 0; } int main() { int a,b,c,d,x,y,t; while(scanf("%d%d%d",&N,&M,&T)!=EOF) {getchar(); if(N==0&&M==0&&T==0) break; for(a=0;a<N;a++) { for(b=0;b<M;b++) { scanf("%c",&ch[a][b]); if(ch[a][b]=='S'){x=a;y=b;} }getchar(); } w=0; t=1; DFS(x,y,t); if(w==1) printf("YES\n"); else printf("NO\n"); } return 0; }