題意：一個N*M的地圖，走過的點不能再走，X為牆不可走，能否從點S到點D恰好用時T。（1 < N, M < 7; 0 < T < 50）
——>>有點邯鄲學步的感覺，寒假時用cin輸入數據，輕松AC，後來慢慢改成了用scanf來輸入，今天，這道坑爹的題目交了n次也是WA，代替了n種方式後發現，是輸入的問題，猜想是輸入的地圖有空格……
超時優化的思想：
1、可走格子數少於T時，一定不ok；
2、從格子A到格子B，無論怎麼走，步數的奇偶性相同。
用時很少的寫法：
[cpp] #include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
char MAP[8][8];
int N, M, T, s_x, s_y, d_x, d_y;
int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0, -1};
bool ok;
void dfs(int x, int y, int cur)
{
if(ok) return;
int temp = T - cur - abs(d_x-x) - abs(d_y-y);
if((temp < 0) || (temp % 2 == 1)) return;
for(int i = 0; i < 4; i++)
{
int new_x = x + dx[i];
int new_y = y + dy[i];
if(new_x >= 0 && new_x < N && new_y >= 0 && new_y < M && MAP[new_x][new_y] != 'X')
{
if(new_x == d_x && new_y == d_y && cur+1 == T) ok = 1;
else
{
MAP[new_x][new_y] = 'X';
dfs(new_x, new_y, cur+1);
MAP[new_x][new_y] = '.';
}
}
}
}
int main()
{
int i, j, sum;
while(scanf("%d%d%d", &N, &M, &T) == 3)
{
if(N == 0 && M == 0 && T == 0) return 0;
sum = 1;
for(i = 0; i < N; i++)
{
//getchar();
for(j = 0; j < M; j++)
{
//MAP[i][j] = getchar();
//scanf("%c", &MAP[i][j]);
cin>>MAP[i][j];
if(MAP[i][j] == 'S')
{
s_x = i;
s_y = j;
}
else if(MAP[i][j] == 'D')
{
d_x = i;
d_y = j;
}
else if(MAP[i][j] == 'X') sum++;
}
}
sum = N*M - sum;
ok = 0;
MAP[s_x][s_y] = 'X';
if(T <= sum)
dfs(s_x, s_y, 0);
if(ok) printf("YES\n");
else printf("NO\n");
}
return 0;
}
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
char MAP[8][8];
int N, M, T, s_x, s_y, d_x, d_y;
int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0, -1};
bool ok;
void dfs(int x, int y, int cur)
{
if(ok) return;
int temp = T - cur - abs(d_x-x) - abs(d_y-y);
if((temp < 0) || (temp % 2 == 1)) return;
for(int i = 0; i < 4; i++)
{
int new_x = x + dx[i];
int new_y = y + dy[i];
if(new_x >= 0 && new_x < N && new_y >= 0 && new_y < M && MAP[new_x][new_y] != 'X')
{
if(new_x == d_x && new_y == d_y && cur+1 == T) ok = 1;
else
{
MAP[new_x][new_y] = 'X';
dfs(new_x, new_y, cur+1);
MAP[new_x][new_y] = '.';
}
}
}
}
int main()
{
int i, j, sum;
while(scanf("%d%d%d", &N, &M, &T) == 3)
{
if(N == 0 && M == 0 && T == 0) return 0;
sum = 1;
for(i = 0; i < N; i++)
{
//getchar();
for(j = 0; j < M; j++)
{
//MAP[i][j] = getchar();
//scanf("%c", &MAP[i][j]);
cin>>MAP[i][j];
if(MAP[i][j] == 'S')
{
s_x = i;
s_y = j;
}
else if(MAP[i][j] == 'D')
{
d_x = i;
d_y = j;
}
else if(MAP[i][j] == 'X') sum++;
}
}
sum = N*M - sum;
ok = 0;
MAP[s_x][s_y] = 'X';
if(T <= sum)
dfs(s_x, s_y, 0);
if(ok) printf("YES\n");
else printf("NO\n");
}
return 0;
}
vis[][]數組寫法：
[cpp] #include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 7 + 10;
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0, -1, 1};
char MAP[maxn][maxn];
bool ok, vis[maxn][maxn];
int N, M, T, Dx, Dy;
void dfs(int x, int y, int cur)
{
if(ok) return;
if(cur == T)
{
if(x == Dx && y == Dy)
{
ok = 1;
return;
}
else
return;
}
int temp = T - cur - (Dx - x) - (Dy - y);
if(temp < 0 || (temp&1)) return;
for(int i = 0; i < 4; i++)
{
int newx = x + dx[i];
int newy = y + dy[i];
if(newx >= 0 && newx < N && newy >= 0 && newy < M && MAP[newx][newy] != 'X' && !vis[newx][newy])
{
vis[newx][newy] = 1;
dfs(newx, newy, cur+1);
vis[newx][newy] = 0;
}
}
}
int main()
{
int Sx, Sy, i, j;
while(scanf("%d%d%d", &N, &M, &T) == 3)
{
if(!N && !M && !T) return 0;
for(i = 0; i < N; i++)
{
for(j = 0; j < M; j++)
{
cin>>MAP[i][j];
if(MAP[i][j] == 'S')
{
Sx = i;
Sy = j;
}
else if(MAP[i][j] == 'D')
{
Dx = i;
Dy = j;
}
}
}
ok = 0;
memset(vis, 0, sizeof(vis));
vis[Sx][Sy] = 1;
dfs(Sx, Sy, 0);
if(ok)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 7 + 10;
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0, -1, 1};
char MAP[maxn][maxn];
bool ok, vis[maxn][maxn];
int N, M, T, Dx, Dy;
void dfs(int x, int y, int cur)
{
if(ok) return;
if(cur == T)
{
if(x == Dx && y == Dy)
{
ok = 1;
return;
}
else
return;
}
int temp = T - cur - (Dx - x) - (Dy - y);
if(temp < 0 || (temp&1)) return;
for(int i = 0; i < 4; i++)
{
int newx = x + dx[i];
int newy = y + dy[i];
if(newx >= 0 && newx < N && newy >= 0 && newy < M && MAP[newx][newy] != 'X' && !vis[newx][newy])
{
vis[newx][newy] = 1;
dfs(newx, newy, cur+1);
vis[newx][newy] = 0;
}
}
}
int main()
{
int Sx, Sy, i, j;
while(scanf("%d%d%d", &N, &M, &T) == 3)
{
if(!N && !M && !T) return 0;
for(i = 0; i < N; i++)
{
for(j = 0; j < M; j++)
{
cin>>MAP[i][j];
if(MAP[i][j] == 'S')
{
Sx = i;
Sy = j;
}
else if(MAP[i][j] == 'D')
{
Dx = i;
Dy = j;
}
}
}
ok = 0;
memset(vis, 0, sizeof(vis));
vis[Sx][Sy] = 1;
dfs(Sx, Sy, 0);
if(ok)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
